Shortest Path in Binary Matrix
Problem Statement
You are given an n x n binary matrix grid where 0 means open and 1 means blocked.
A clear path starts at the top-left cell (0, 0), ends at the bottom-right cell (n - 1, n - 1), and only moves through open cells. From a cell you may move in 8 directions: horizontal, vertical, or diagonal.
Return the length of the shortest clear path, measured as the number of cells in the path. Return -1 if no clear path exists.
Input
A square integer matrix grid containing only 0 and 1. The start is grid[0][0] and the target is grid[n - 1][n - 1].
Output
An integer: the minimum number of cells in any valid 8-directional clear path, or -1 when no such path exists.
Constraints
- •
n == grid.length - •
n == grid[i].length - •
1 <= n <= 100 - •
grid[i][j] is 0 or 1
Examples
Example 1
grid = [[0,1],[1,0]]
2Example 2
grid = [[0,0,0],[1,1,0],[1,1,0]]
4Example 3
grid = [[1,0,0],[1,1,0],[1,1,0]]
-1Learning Objectives
- Recognise a binary grid as an unweighted graph where open cells are nodes and valid moves are edges.
- Use BFS to guarantee the first time the target is reached is the shortest path length.
- Handle 8-directional movement cleanly with a fixed neighbour array instead of writing eight separate checks.
- Decide whether to mark visited in-place or with a separate boolean matrix based on whether mutation is acceptable.
Intuition
Every open cell is a room, and each allowed move is a hallway with the same cost: one step into the next cell. When all edges have equal weight, BFS is the right mental model because it explores in expanding rings: first every cell at distance 1, then every cell at distance 2, and so on.
That ring property is the whole proof. If the target is popped from the queue at distance d, every path with fewer than d cells would have been discovered in an earlier ring. There is no need for Dijkstra because there are no different edge weights to compare.
The detail that changes this from many grid BFS problems is the neighbour set. This problem is 8-directional, so diagonals count. A two-by-two grid with open opposite corners has answer 2, not -1 and not 3.
Recognise the pattern: shortest path in an unweighted grid or graph means BFS with distance stored by level or carried in the queue.
Common mistakes
- ×Using only four directions and accidentally rejecting valid diagonal paths.
- ×Returning the number of moves instead of the number of cells. The start cell counts, so a 1x1 open grid returns 1.
- ×Marking visited when a cell is dequeued instead of when it is enqueued, allowing the same cell to enter the queue many times.
- ×Forgetting to reject a blocked start or blocked target before starting BFS.
- ×Using DFS and hoping the first path found is shortest; DFS has no shortest-path guarantee in an unweighted graph.
Algorithm Explanation
- Let n be the grid size. If the start or target cell is blocked, return -1.
- Create a queue of states containing row, column, and distance. Seed it with (0, 0, 1) because the path already includes the start cell.
- Mark the start visited immediately. The shown solution mutates the grid by setting visited open cells to 1; a separate visited matrix is equivalent.
- Repeatedly pop the next cell. If it is the target, return its distance.
- For each of the eight directions, if the neighbour is inside the grid and still open, mark it visited and enqueue it with distance + 1.
- If the queue empties, every reachable open cell was explored and the target was not reached, so return -1.
Solutions
Solution: BFS with 8-directional moves
Use this whenever every move has the same cost. It is optimal, simpler than Dijkstra, and directly matches the unweighted shortest-path guarantee.
Treat each open cell as a node in an unweighted graph. BFS expands cells by increasing path length, so the first time the target is removed from the queue is the shortest clear path. Mutating open cells to 1 is a compact visited marker; use boolean[][] visited if the input must be preserved.
Step-by-step
- Reject blocked endpoints.
- Push the start with distance 1 and mark it visited.
- Pop cells from the queue in FIFO order.
- For each of the eight directions, enqueue unvisited open neighbours with distance + 1.
- Return as soon as the target is popped; otherwise return -1 after the queue drains.
O(n²)
O(n²)
Each cell is enqueued at most once, and the queue can hold O(n²) cells in the worst case.
Java implementation
Dry Run
Sample input
Trace BFS on grid = [[0,0,0],[1,1,0],[1,1,0]].
| Step | Popped cell | Distance | New cells enqueued | Queue after step |
|---|---|---|---|---|
| 1 | (0,0) | 1 | (0,1) | [(0,1,d=2)] |
| 2 | (0,1) | 2 | (0,2), (1,2) | [(0,2,d=3), (1,2,d=3)] |
| 3 | (0,2) | 3 | none, neighbours are blocked or visited | [(1,2,d=3)] |
| 4 | (1,2) | 3 | (2,2) | [(2,2,d=4)] |
| 5 | (2,2) | 4 | target reached | return 4 |
The queue processes all distance-2 cells before any distance-3 cell, and all distance-3 cells before distance 4. Therefore reaching (2,2) at distance 4 proves that no shorter clear path exists.
Interview Tips
Say the phrase unweighted shortest path early, then state that BFS is optimal because it explores by increasing distance. Confirm whether you may mutate the grid; if not, use a visited matrix without changing the algorithm. Call out the 8-directional neighbour array explicitly because many candidates lose the diagonal moves. For follow-ups with different move costs, explain that the solution would move from BFS to Dijkstra.
Likely follow-ups
- Return the actual path, not only its length. Store a parent coordinate for each visited cell and reconstruct from the target.
- What if diagonal moves cost more than horizontal moves? Use Dijkstra because edges are no longer uniform.
- What if some cells are unlocked after collecting keys? Add the key mask to the BFS state.
- Can you solve without mutating grid? Replace in-place marking with a boolean visited matrix.
Similar Problems
Key Takeaways
- BFS is the shortest-path algorithm for unweighted graphs.
- The path length counts cells, so the start contributes distance 1.
- Mark visited when enqueuing to prevent duplicate frontier entries.
- The neighbour set is part of the graph definition; here it has eight directions.