Shortest path through a grid with BFS

Question

A robot in a warehouse grid must travel from start to goal. Cells marked 1 are blocked; moves are up/down/left/right, one cell per step.

grid = [[0, 0, 1],
        [0, 1, 0],
        [0, 0, 0]]
start = (0, 0), goal = (2, 2)
-> 4            # down, down, right, right

Return the minimum number of steps, or -1 if unreachable. Aim for $O(nm)$ .

Accepted Answer

When every move costs the same, breadth-first search explores cells in increasing distance from the start: first all cells 1 step away, then 2, and so on. The first time the goal is dequeued, its recorded distance is provably minimal. DFS gives no such guarantee, it finds a path, not the shortest, and Dijkstra is overkill when all edge weights are 1. The one detail that separates clean BFS from buggy BFS: mark a cell visited when you enqueue it, not when you dequeue it. Marking late lets the same cell be enqueued many times, inflating the queue to O((nm)^2) in bad cases. On the example, BFS r…

Shortest path through a grid with BFS

Your answer

More Coding questions