Shortest Path in Binary Matrix
In an n × n grid of 0s (open) and 1s (blocked), find the length of the shortest path from the top-left to the bottom-right cell moving in any of the 8 directions through open cells only. Length counts cells visited; return -1 if there is no path.
- 1 ≤ n ≤ 100
- grid[i][j] ∈ {0, 1}
- Shortest path on a grid
- All moves cost one
- Explore cells in order of distance with a queue
BFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.
If the start or end cell is blocked return -1. Otherwise run BFS from the top-left, marking cells visited when enqueued and tracking distance per layer. Expand each cell into its 8 in-bounds open neighbours. The first time the bottom-right cell is dequeued its distance is the answer, since BFS discovers cells in non-decreasing distance order.
- A* with Chebyshev distance heuristic reaches the goal faster on open grids while staying optimal. Dijkstra is unnecessary because all edges are unit weight.