DSA Factory
Free Graphs lessonsGraphs · Stage 5 · Shortest paths · Step 4

When some steps are free

Use a double-ended line so that free moves go to the front and costly moves go to the back. About 15 minutes.

Some steps cost nothing

In a maze with breakable walls, stepping into an open cell costs 0 and stepping into a wall costs 1, because you must break it. You want the path with the fewest broken walls, not the fewest steps.

The ring idea almost works, but now a neighbour can be reached at the same cost as the cell you stand on. It belongs in the current ring, not the next one. The fix is a line you can add to at both ends: free moves go in the front, so they are handled right away, and costly moves go in the back.

Free move: joins the front of the line.
Costly move: joins the back of the line.
In code
line = deque()
line.appendleft(cell)    # free: the front
line.append(cell)        # costly: the back
0 is open, 1 is a wall to break. Fewest walls from the top-left to the bottom-right.
012
0
0
1
0
1
0
1
1
2
0
0
0
line
[(0,0)]

Start at the top-left with 0 broken walls so far.

Move 1 of 4

Improve, then add

A cell can be reached more than one way, and a later way might be cheaper. So start every distance at a huge number, and whenever the cost to a neighbour through the current cell is smaller than what it has, update it and add it to the line.

This cell may be added twice, once expensive and once cheap, and that's fine. The cheaper version arrives first, because it was added to the front, and the stale one is harmless since it can't improve anything.

Start at infinity: so any real cost looks like an improvement.
Only add on improvement: otherwise skip.
In code
if d + cost < best:
    best = d + cost
Quick check

A neighbour can be entered at no cost. Where should it go in the line?

  1. AAt the front, because it is as close as the cell you're on
  2. BAt the back, like any other place
  3. CNowhere, since it costs nothing
Show the answer

At the front, because it is as close as the cell you're on. Free moves keep the same cost, so they are handled before costlier places.

Your problem

Fewest walls to break

maze is a grid where 0 is an open cell and 1 is a wall. You start at the top-left cell and want the bottom-right cell, moving one step at a time up, down, left or right. You can walk through a wall, but each wall cell you enter counts as one broken wall. Return the fewest walls you must break. The start and exit are open cells.

Example
maze = [[0, 1, 0], [0, 1, 1], [0, 0, 0]] → 0

1 ≤ rows, columns ≤ 20 · the start and exit are open

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve