Given an n x n binary matrix grid, return the length of the shortest clear path from top-left (0,0) to bottom-right (n-1,n-1). A clear path consists of cells with value 0, and you can move in 8 directions (including diagonals). The path length is the number of cells visited. Return -1 if no such path exists.

Examples

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2
Explanation: Path (0,0) → (1,1), length = 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Explanation: Path (0,0) → (0,1) → (0,2) → (1,2) → (2,2), but
             shorter: (0,0) → (0,1) → (1,2) → (2,2), length = 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
Explanation: Starting cell is blocked.

Constraints

  • n == grid.length == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] is 0 or 1

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Queue BFS (this problem) O(n) O(n) Shortest path in unweighted graphs
Multi-source BFS O(n) O(n) Start from all sources simultaneously
0-1 BFS / deque O(n) O(n) Weights 0 or 1
Level-order BFS O(n) O(w) Process by depth/layer

Thinking Process

Why BFS?

This is an unweighted shortest path problem on a grid. BFS explores all cells at distance d before any cell at distance d+1, guaranteeing the first time we reach the destination is the shortest path.

8-Directional Movement

Unlike typical grid BFS (4 directions), this problem allows diagonal movement. This means 8 neighbors per cell.

Edge Cases

  • Start or end cell is 1 (blocked) → return -1 immediately
  • Grid is 1x1 with grid[0][0] = 0 → return 1
Grid traversal BFS/DFS flood from each cell

Approach: BFS – O(n^2)

Input: grid = [
  [0,1],
  [1,0]
]
Output: 2
# Path: (0,0) → (1,1)

Solution Explanation

Approach: Queue BFS (this problem)

Key idea: ### Why BFS?

How the code works:

  • Start or end cell is 1 (blocked) → return -1 immediately
  • Grid is 1x1 with grid[0][0] = 0 → return 1

Walkthrough — input grid = [[0,1],[1,0]], expected output 2:

Path (0,0) → (1,1), length = 2

Common Mistakes

  • Forgetting to check both start and end cells (either being blocked means no path)
  • Using DFS instead of BFS (DFS doesn’t guarantee shortest path in unweighted graphs)
  • Marking visited when popping instead of when pushing (causes duplicate entries and TLE)
  • Only checking 4 directions instead of 8

Key Takeaways

  • BFS on grid = shortest path when all moves have equal cost
  • Mark cells as visited when enqueueing, not when dequeuing – this prevents the same cell from being added multiple times
  • The path length counts cells visited (not edges), so start at distance 1

References

Template Reference