Shortest way through a maze
Use the ripple search on a grid of open cells and walls to find the fewest steps from corner to corner. About 14 minutes.
Cells in the line
The search is the one you know, with cells as the places. The line holds cells, each written as a row and column pair. Take a cell from the front, look at the four cells around it, and for each one that is on the map, open, and not yet reached, write its distance and add it to the back.
A wall is a cell you can never enter. A cell that is already reached is skipped. Those two checks are the whole difference between a maze and a plain graph.
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in dirs:
nr, nc = r + dr, c + dc- queue
- [(0,0)]
Start at the top-left with distance 0. The walls are the cells holding 1.
Check the corners first
A maze can be impossible in two quick ways. The start cell may itself be a wall, or the exit may be one. Both give an answer of -1 before you search at all.
Otherwise run the search until the line is empty. If the exit still has -1 written on it, no chain of open cells links the corners, and -1 is the right answer too. Notice there's no need for a special case for "no path". The search simply never reached it.
In a maze where the start cell is itself a wall, what is the fewest number of steps?
- A-1, because you cannot stand on a wall
- B0, because you haven't moved yet
- C1, you step off the wall
Show the answer
-1, because you cannot stand on a wall. With no legal starting cell there is no route at all.
Fewest steps through the maze
maze is a grid where 0 is an open cell and 1 is a wall. You start at the top-left cell and want to reach the bottom-right cell, moving one step at a time up, down, left or right through open cells. Return the fewest steps needed, or -1 if it is impossible. When the grid has a single open cell, the answer is 0.
maze = [[0, 0, 1], [1, 0, 0], [0, 1, 0]] → 4
1 ≤ rows, columns ≤ 20 · each cell is 0 or 1