Shortest Path in Binary Matrix

Problem

You are given an n x n binary matrix grid where 0 represents a free cell and 1 represents a blocked cell.

Find the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). A clear path is one where every cell on the path is 0.

You may move in 8 directions (horizontally, vertically, and diagonally) from any free cell.

Return the length of the shortest clear path (in terms of number of cells visited). If no such path exists, return -1.

Input / Output Format

Input: grid — a 2D list of integers containing only 0s and 1s.

Output: An integer — the number of cells in the shortest clear path, or -1 if impossible.

Examples

Example 1

Input: grid = [[0,1],[1,0]] Output: 2 Explanation: The path goes (0,0) → (1,1) diagonally. Both cells are 0. The path length is 2.

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]] Output: 4 Explanation: The shortest path is (0,0) → (0,1) → (0,2) → (1,2) → (2,2) — but that's 5 cells. The optimal is (0,0) → (0,1) → (1,2) → (2,2) using diagonal moves — 4 cells total.

Example 3

Input: grid = [[1,0,0],[1,1,0],[1,1,0]] Output: -1 Explanation: The starting cell (0,0) is blocked (1), so no path is possible.

Approach Hints

Why BFS (Not DFS)?

BFS explores cells level by level, guaranteeing the first time it reaches the destination is via the shortest path. DFS does not have this property — it may find a path, but not necessarily the shortest one.

Common Mistakes to Avoid

1. Forgetting to check the start/end cells: If grid[0][0] == 1 or grid[n-1][n-1] == 1, return -1 immediately.
2. Revisiting cells: Mark a cell as visited when you enqueue it, not when you dequeue it. Marking on dequeue can lead to exponential re-processing.
3. Using DFS instead of BFS: DFS cannot guarantee shortest path in unweighted graphs.