Shortest Path in Binary Matrix
Understanding the Problem
We have an n x n grid of 0s and 1s, and we need to find the shortest path from the top-left corner to the bottom-right corner. The path can only go through cells with value 0, and we can move in all 8 directions (up, down, left, right, and the four diagonals). The "length" of the path is the count of cells visited, including both the start and end cells.
Three details shape the solution. First, movement is 8-directional, so from any cell there are up to 8 neighbors to consider, not 4. Second, we want the shortest path, not any path. Third, the path length counts cells, not edges, so a path from (0,0) to (0,0) in a 1x1 grid has length 1.
Every move costs the same (one cell), so the grid is an unweighted graph: each 0-cell is a node, and each adjacent pair of 0-cells shares an edge of weight 1. BFS finds shortest paths in unweighted graphs by exploring level by level, so the first time it reaches the destination it has used the fewest cells possible.
Key Constraints:
1 <= n <= 100-> At most 100 x 100 = 10,000 cells. An O(n^2) traversal over all cells is fast, and the heavier O(n^2 log n) variant still finishes well within limits.grid[i][j] is 0 or 1-> A cell is either passable (0) or blocked (1).
Approach 1: BFS (Breadth-First Search)
Intuition
BFS processes all cells at distance 1 first, then all cells at distance 2, and so on. The first time it reaches the bottom-right corner, it has used the fewest cells possible, because any shorter path would have arrived in an earlier layer.
The expansion is like a ripple from a stone dropped in water: it grows outward one layer at a time, evenly in all directions. The first layer to touch the destination is the shortest path.
We treat the grid as a graph. Each cell with value 0 is a node. Each pair of adjacent 0-cells (in all 8 directions) is connected by an edge. We start BFS from (0, 0), explore all reachable neighbors, and track the distance. When we reach (n-1, n-1), we return that distance.
BFS processes all nodes at distance d before any node at distance d+1. When it first dequeues the bottom-right cell, no shorter path to it can exist, because such a path would have placed it in an earlier layer.
Marking a cell as visited when it enters the queue, not when it leaves, keeps each cell out of the queue more than once. Several neighbors processed in the same layer can point at the same cell, and the first one to reach it already records the optimal distance, so later attempts would only add duplicate work.
Algorithm
- Check if the start cell
grid[0][0]or the end cellgrid[n-1][n-1]is 1. If either is blocked, return -1 immediately. - Create a queue and add the starting cell (0, 0) with distance 1 (since the path length includes the starting cell).
- Mark (0, 0) as visited by setting
grid[0][0] = 1. - While the queue is not empty, dequeue a cell (row, col) with its current distance.
- If (row, col) is the bottom-right cell, return the current distance.
- For each of the 8 neighbors (newRow, newCol), check if it's within bounds and has value 0. If so, add it to the queue with distance + 1 and mark it as visited.
- If the queue empties without reaching (n-1, n-1), return -1.
Example Walkthrough
Code
- Time Complexity: O(n^2). Each cell is added to the queue at most once and processed at most once. For each cell, we check 8 neighbors, which is O(1) work per cell. With n^2 cells total, the overall time is O(n^2).
- Space Complexity: O(n^2). In the worst case, the queue could hold all n^2 cells. We reuse the input grid for visited tracking, so no extra visited array is needed, but the queue itself takes O(n^2) space.
BFS explores cells in concentric layers from the start, spending work on cells that lead away from the destination. The next approach directs exploration toward the goal instead.
Approach 2: A* Search (Optimized BFS)
Intuition
BFS explores in all directions equally, even though the destination is fixed at the bottom-right corner. A* adds a sense of direction: it prioritizes cells that look closer to the goal, using a heuristic to estimate the remaining distance and processing the most promising cells first.
For a grid with 8-directional movement, the heuristic is the Chebyshev distance (the chessboard distance): max(|row - targetRow|, |col - targetCol|). This is the minimum number of moves a king on a chessboard would need to reach the target. It never overestimates the true remaining distance, which is what keeps A* correct while letting it skip cells BFS would have visited.
The priority of each cell is distance_so_far + heuristic_estimate. Cells that have made the most progress toward the goal are dequeued first.
A* returns the optimal path when its heuristic is admissible (never overestimates the remaining distance). With 8-directional movement and no obstacles, the fewest moves from any cell to the bottom-right corner is exactly max(|row - (n-1)|, |col - (n-1)|). Obstacles can only lengthen a path, so the Chebyshev estimate is always at most the true remaining cost. An admissible heuristic guarantees that the first time the destination is dequeued, its recorded distance is the shortest.
The benefit over BFS is fewer cells expanded, especially in large open grids: A* steers toward the goal instead of radiating outward in every direction.
Algorithm
- Check if the start or end cell is blocked. If so, return -1.
- Create a
dist[][]array initialized to infinity. Setdist[0][0] = 1. - Create a min-heap (priority queue) ordered by
distance + heuristic. Add (0, 0) with distance 1. - While the priority queue is not empty, extract the cell with the smallest priority.
- If it's the destination, return the distance.
- If the popped distance is greater than
dist[row][col], skip it (stale entry). - For each of the 8 valid neighbors, if
dist + 1 < dist[neighbor], updatedist[neighbor]and add it to the priority queue with priority(dist + 1) + chebyshev_distance(neighbor, destination). - If the priority queue empties without reaching the destination, return -1.
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). In the worst case, A visits O(n^2) cells. Each priority queue operation costs O(log n^2) = O(log n). In practice, A usually explores far fewer cells than BFS.
- Space Complexity: O(n^2). The priority queue can hold up to O(n^2) cells in the worst case, same as BFS.