Shortest Path in Binary Matrix

Shortest Path in Binary Matrix medium

Description

Given an n × n binary matrix grid, return the length of the shortest clear path from top-left (0, 0) to bottom-right (n-1, n-1). If such a path does not exist, return -1.

A clear path is a sequence of cells such that:

All visited cells are 0.
Adjacent cells are 8-directionally connected (horizontal, vertical, or diagonal neighbors).
The path length is the number of cells visited.

Examples

> Case 1:
    grid = [[0,1],[1,0]]
    Output: 2
 
> Case 2:
    grid = [[0,0,0],[1,1,0],[1,1,0]]
    Output: 4
    # Path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
 
> Case 3:
    grid = [[1,0,0],[1,1,0],[1,1,0]]
    Output: -1   # starting cell blocked

Constraints

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

State design

Every move costs 1 → BFS. The graph is implicit: vertices are passable cells, edges go to the 8 neighbors that are also passable.

Standard BFS shortest path, just with 8 directions instead of 4. Watch for the “starting or ending cell is blocked” edge case.

Code

Analysis

Time: O(n²) — at most every cell is enqueued once, each scan checks 8 neighbors.
Space: O(n²) for the distance array.

Path length = number of cells, not edges. Initialize dist[0][0] = 1, not 0. This is the most common off-by-one in this problem.

Same skin

Walls and Gates — multi-source BFS from every gate.
01 Matrix — multi-source BFS from every 0.
Rotting Oranges — multi-source BFS from every rotten orange; track time as BFS layer.
Shortest Bridge — DFS to find one island, then BFS outward to find the other.

Network Delay Time Cheapest Flights Within K Stops