Shortest Path in Binary Matrix: 8-Directional BFS

You are given an n x n binary matrix grid. 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 consists only of cells with value 0, and you can move in all 8 directions (horizontally, vertically, and diagonally). The path length is the number of cells visited. If no such path exists, return -1.

This is LeetCode 1091: Shortest Path in Binary Matrix, and it is one of the cleanest problems for learning BFS on a grid with 8-directional movement. The technique it teaches applies to any problem where you need the shortest path in an unweighted grid.

Why this problem matters

Grid shortest-path problems show up constantly in interviews and competitive programming. Most grid BFS problems only use 4-directional movement (up, down, left, right), but this one adds diagonals. That small change forces you to think carefully about neighbor generation and makes the problem a better test of your BFS fundamentals.

Once you can handle 8-directional BFS here, you can adapt the same template to problems like "Shortest Bridge" (LeetCode 934), "Rotting Oranges" (LeetCode 994), and any grid problem where you need to find minimum distance.

The key insight

BFS guarantees the shortest path in an unweighted graph. Every cell in the grid is a node, and every valid move to an adjacent 0-cell is an edge with weight 1. When you process nodes level by level, the first time you reach any cell is guaranteed to be via the shortest path. This is the fundamental property that makes BFS the right tool here, not DFS, not Dijkstra.

The algorithm:

1. Check if the start (0, 0) or end (n-1, n-1) is blocked. If either is 1, return -1 immediately.
2. Initialize a queue with (0, 0, 1) where 1 is the path length so far. Mark the start as visited.
3. For each cell you dequeue, check all 8 neighbors. If a neighbor is in bounds, unvisited, and has value 0, mark it visited and enqueue it with distance + 1.
4. When you dequeue (n-1, n-1), return the distance. If the queue empties without reaching it, return -1.

The solution

from collections import deque

def shortest_path_binary_matrix(grid: list[list[int]]) -> int:
    n = len(grid)
    if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
        return -1

    queue = deque([(0, 0, 1)])
    grid[0][0] = 1
    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:
                grid[nr][nc] = 1
                queue.append((nr, nc, dist + 1))

    return -1

Let's walk through what each piece does.

The first check handles the edge case where the start or end cell is blocked. If grid[0][0] is 1 or grid[n-1][n-1] is 1, there is no valid path, so we return -1 right away.

We initialize the BFS queue with the starting cell (0, 0) and a distance of 1 (the path includes the starting cell itself). We mark it visited by setting grid[0][0] = 1. This is a common trick: instead of using a separate visited set, we modify the grid in place, turning 0 cells into 1 cells as we visit them. This saves space and simplifies the code.

The directions list contains all 8 possible moves. Each tuple (dr, dc) represents a row and column offset. This covers horizontal, vertical, and diagonal neighbors.

The BFS loop dequeues a cell, checks if it is the target, and then explores all 8 neighbors. For each neighbor that is in bounds and still 0 (unvisited and not blocked), we mark it as 1 and enqueue it with dist + 1. Marking before enqueueing prevents the same cell from being added to the queue multiple times.

If the queue empties without ever reaching (n-1, n-1), the target is unreachable and we return -1.

Visual walkthrough

Let's trace through a 3x3 grid step by step. The grid has blocked cells at (1,0), (1,1), (2,0), and (2,1). Watch how BFS explores the 8-directional neighborhood at each step, using diagonal moves to route around the blocked cells.

Notice that at step 3, BFS enqueues both (0,2) and (1,2) at the same distance. Both are valid 0-cells reachable from (0,1), one horizontally and one diagonally. BFS processes them in order, and (1,2) is the one that eventually leads to the target via (2,2). The diagonal move from (0,1) to (1,2) is what makes the shortest path possible in this grid.

Complexity analysis

Time is O(n^2) because the grid has n^2 cells and each cell is visited at most once. We mark cells as visited before enqueueing, so no cell enters the queue twice. Each cell does constant work (checking 8 neighbors), making the total work proportional to n^2.

Space is O(n^2) in the worst case. If every cell is 0, the BFS frontier could grow to include a large portion of the grid. The queue holds at most O(n^2) entries. We reuse the input grid for visited marking, so no additional visited structure is needed.

The building blocks

1. 8-directional movement

The pattern of encoding all 8 neighbor offsets in a list:

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

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < n and 0 <= nc < n:
        process(nr, nc)

This is the standard way to iterate over neighbors in a grid. For 4-directional problems, you drop the four diagonal entries. For 8-directional problems like this one, you include all eight. The bounds check 0 <= nr < n and 0 <= nc < n prevents going out of the grid. You will reuse this exact pattern in almost every grid traversal problem.

2. BFS shortest path

The pattern of using BFS to find shortest distance in an unweighted graph:

queue = deque([(start, 1)])
visited.add(start)

while queue:
    node, dist = queue.popleft()
    if node == target:
        return dist
    for neighbor in get_neighbors(node):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append((neighbor, dist + 1))

BFS processes nodes in order of distance from the source. The first time you reach any node, it is via the shortest path. This property holds because every edge has the same weight. You will use this template for "Open the Lock," "Word Ladder," and any problem asking for minimum steps in an unweighted graph.

3. In-place visited marking

Instead of maintaining a separate visited set, you can mark cells directly in the grid by changing their value:

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

This saves O(n^2) space for the visited set and eliminates hash lookups. The tradeoff is that you modify the input. In an interview, mention this tradeoff and ask if modifying the input is acceptable. If not, use a separate set or a copy of the grid.

Edge cases

Before submitting, think through these scenarios:

• Start or end is blocked: grid[0][0] == 1 or grid[n-1][n-1] == 1. Return -1 immediately.
• Single cell grid: grid = [[0]]. The start is the end. Return 1 (the path includes the cell itself).
• Single cell blocked: grid = [[1]]. Return -1.
• No path exists: All routes to (n-1, n-1) are blocked by 1 cells. BFS exhausts the queue and returns -1.
• Entire grid is open: grid is all 0 cells. The shortest path is the diagonal, length n (moving diagonally from corner to corner).
• Large grid: n = 100. BFS visits at most 10,000 cells, which runs well within time limits.

From understanding to recall

You have seen how 8-directional BFS finds the shortest clear path through a binary matrix. The code is short and the logic is clean. But reproducing it from memory under interview pressure is a different skill entirely.

The details that trip people up are small but costly. Do you include the starting cell in the distance count? Do you mark visited before or after enqueueing? Do you check for the target when enqueueing or when dequeuing? Getting any of these wrong gives you a subtly broken solution that passes some test cases but fails others.

Spaced repetition is how you lock in these details. You practice writing the 8-directional neighbor loop, the BFS queue setup, and the visited marking from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "shortest path in a grid" in a problem statement, and the BFS template flows out without hesitation.

Related posts

• Rotting Oranges - Multi-source BFS on a grid with level-by-level processing
• Number of Islands - Grid traversal using DFS flood fill
• Open the Lock - BFS shortest path in an implicit graph

CodeBricks breaks Shortest Path in Binary Matrix into its 8-directional movement and BFS shortest path building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid BFS problem shows up in your interview, you do not think about it. You just write it.