Shortest Path in Binary Matrix — BFS Solution

Intermediate 15 min read

What you'll learn

✓BFS for shortest path on a grid with 8-directional movement
✓Why BFS guarantees shortest path in unweighted grids
✓Handling start and end corner cases
✓Optimization techniques for grid BFS

Prerequisites

•BFS pattern — see BFS with Queues

BFS finding shortest path in binary matrix

Given an n×n binary matrix where 0 is open and 1 is blocked, find the length of the shortest clear path from top-left (0,0) to bottom-right (n-1,n-1). You can move in 8 directions (including diagonals). The path length is the number of cells visited.

Solution

from collections import deque

def shortest_path_binary_matrix(grid):
    """
    Find shortest clear path in binary matrix.
    Time: O(n²), Space: O(n²)
    """
    n = len(grid)

    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    if n == 1:
        return 1

    queue = deque([(0, 0, 1)])  # row, col, path_length
    grid[0][0] = 1  # Mark visited

    directions = [
        (-1,-1), (-1,0), (-1,1),
        (0,-1),          (0,1),
        (1,-1),  (1,0),  (1,1)
    ]

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            if (0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0):
                if nr == n-1 and nc == n-1:
                    return dist + 1

                grid[nr][nc] = 1  # Mark visited
                queue.append((nr, nc, dist + 1))

    return -1

Trace

Grid:          BFS expansion (distance from start):
0 0 0          1 2 3
1 1 0    →     .  .  3
0 0 0          .  4 4

Shortest path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2) = length 5
Wait — let's check with diagonals:
(0,0)→(0,1)→(1,2)→(2,2) would be length 4

BFS ensures we find 4 first.

Without Modifying the Grid

If you can’t modify the input, use a visited set:

def shortest_path_no_modify(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    queue = deque([(0, 0, 1)])
    visited = {(0, 0)}
    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

    while queue:
        r, c, dist = queue.popleft()
        if r == n-1 and c == n-1:
            return dist

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < n and 0 <= nc < n
                and grid[nr][nc] == 0
                and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

    return -1

Edge Cases

Start or end is blocked — return -1 immediately
1×1 grid with 0 — return 1
No path exists — BFS exhausts all reachable cells, return -1
Straight diagonal path — BFS finds it naturally

Complexity

Metric	Value
Time	O(n²) — each cell visited at most once
Space	O(n²) — queue + visited tracking

When to Use This Pattern

Grid BFS is the standard approach for:

Shortest path with uniform cost moves
4-directional or 8-directional movement
Level-by-level exploration of grids

For weighted grids, use Dijkstra’s algorithm instead.

Number of Islands (LeetCode 200) — BFS flood fill
Rotten Oranges (LeetCode 994) — multi-source grid BFS
Shortest Path with Obstacles Elimination (LeetCode 1293)
Maze problems — BFS until wall