Shortest Path in Binary Matrix

Explanation & Solution

Description

Given an n x n binary matrix grid, return 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 in a binary matrix is a path from the top-left cell to the bottom-right cell such that:

All visited cells have a value of 0.
All adjacent cells in the path are 8-directionally connected (i.e., they differ in at most one row and one column).

The length of a clear path is the number of visited cells.

Return -1 if no such path exists.

Examples

Example 1

Input: grid = [[0,1],[1,0]]

Output: 2

Explanation: The shortest clear path is (0,0) → (1,1), which has length 2.

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Explanation: The shortest clear path is (0,0) → (0,1) → (0,2) → (1,2) → (2,2), but a shorter one exists: (0,0) → (0,1) → (1,2) → (2,2) with length 4.

Example 3

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]

Output: -1

Explanation: The top-left cell is 1, so no clear path exists.

Constraints

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

Approach

Graphs pattern

1. Handle Edge Cases

If the start cell grid[0][0] or the end cell grid[n-1][n-1] is 1, return -1 immediately since no clear path can exist.

2. Initialize BFS

Create a queue seeded with the starting cell (0, 0) and an initial distance of 1 (we count the starting cell).
Mark the starting cell as visited by setting it to 1.

3. Process the Queue

Dequeue the front element (row, col, dist).
If we have reached (n-1, n-1), return dist — this is guaranteed to be the shortest path because BFS explores level by level.
Otherwise, explore all 8 neighboring cells.

4. Explore Neighbors

For each of the 8 directions, compute the neighbor coordinates (nr, nc).
If the neighbor is within bounds and its value is 0 (unvisited and clear), mark it as visited and enqueue it with dist + 1.

5. No Path Found

If the queue empties without reaching the destination, return -1.

Key Insight

BFS guarantees the shortest path in an unweighted graph. Each cell is treated as a node, and each valid 8-directional move is an edge of weight 1. The first time BFS reaches the destination, the distance is minimal.

Visualization

Input:

BFS Traversal2×2 grid

output—

Press play to start bfs traversal

CurrentQueuedVisitedSource

7 steps

Solution Code

Word Search

Keys and Rooms