DSA Shortest Path in a Binary Matrix

The problem

Shortest Path in a Binary Matrix gives a square grid of zeros and ones. A zero cell is open and a one cell is blocked.

A path starts at the top-left cell and ends at the bottom-right cell. Each step moves to any of the eight surrounding cells. The answer is the number of cells on the shortest path, counting both ends, or minus one when no path exists.

cases = [
    ([[0, 1], [1, 0]], 2),
    ([[0, 0, 0], [1, 1, 0], [1, 1, 0]], 4),
    ([[0, 1, 1], [1, 1, 0], [1, 1, 0]], -1),
    ([[1, 0], [0, 0]], -1),
]
for grid, expected in cases:
    print("grid", grid, "-> steps:", expected)

The first grid needs the diagonal. Its two open cells touch only at a corner. The fourth grid blocks the start cell itself, so no path can begin.

Intuition: reuse the four-direction search

Grid searches often move in four directions. That habit is the trap here. This problem allows eight directions, and the diagonal is sometimes the whole path.

from collections import deque

grid = [[0, 1], [1, 0]]
seen = {(0, 0)}
queue = deque([(0, 0)])
found = False
while queue:
    r, c = queue.popleft()
    if (r, c) == (1, 1):
        found = True
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 2 and 0 <= nc < 2 and grid[nr][nc] == 0 and (nr, nc) not in seen:
            seen.add((nr, nc))
            queue.append((nr, nc))
print("four-direction answer:", 2 if found else -1)
print("eight-direction answer: 2")

The four-direction search reports no path on a grid whose diagonal path takes two cells. The direction count is part of the problem statement, not a detail.

Brute force: try every path

The brute force walks every possible route. A depth-first walk carries the cells used on the current route, so no route revisits a cell. Each route that reaches the target updates the best length.

def brute(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
        return -1, 0
    best = None
    paths = 0

    def dfs(r, c, length, seen):
        nonlocal best, paths
        if (r, c) == (rows - 1, cols - 1):
            paths += 1
            if best is None or length < best:
                best = length
            return
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    dfs(nr, nc, length + 1, seen)
                    seen.discard((nr, nc))

    dfs(0, 0, 1, {(0, 0)})
    return (best if best is not None else -1), paths

for grid in ([[0, 1], [1, 0]], [[0, 0, 0], [1, 1, 0], [1, 1, 0]]):
    shortest, paths = brute(grid)
    print("shortest:", shortest, "paths tried:", paths)

The method always finds the true shortest path. Its cost is the path count, and open grids hold enormous numbers of paths. The counts here stay small only because these grids are tiny and mostly blocked.

The optimal solution: breadth-first search in eight directions

Breadth-first search expands cells level by level, so the first time it reaches the target, the level number is the shortest path length. That one sentence is the whole method.

A level is one step count. Every cell on a level sits the same number of steps from the start. Marking a cell when it joins the queue keeps it out of later levels.

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
        return -1
    seen = {(0, 0)}
    queue = deque([(0, 0)])
    steps = 1
    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            if (r, c) == (rows - 1, cols - 1):
                return steps
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        if grid[nr][nc] == 0 and (nr, nc) not in seen:
                            seen.add((nr, nc))
                            queue.append((nr, nc))
        steps += 1
    return -1

cases = [
    ([[0, 1], [1, 0]], 2),
    ([[0, 0, 0], [1, 1, 0], [1, 1, 0]], 4),
    ([[0, 1, 1], [1, 1, 0], [1, 1, 0]], -1),
    ([[1, 0], [0, 0]], -1),
]
for grid, expected in cases:
    result = shortest_path(grid)
    print("grid", grid, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass. The blocked-start grid returns minus one before the search begins.

Walkthrough: levels on the second grid

The queue holds one level at a time. Each line below prints the level and its cells, sorted. The target is the bottom-right cell.

from collections import deque

grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]
seen = {(0, 0)}
queue = deque([(0, 0)])
steps = 1
while queue:
    print("step", steps, "cells:", sorted(queue))
    if (2, 2) in queue:
        break
    for _ in range(len(queue)):
        r, c = queue.popleft()
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < 3 and 0 <= nc < 3 and grid[nr][nc] == 0 and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    queue.append((nr, nc))
    steps += 1
print("answer:", steps)

The target appears on level four. No shorter route exists, because levels one to three never contained it. The level number is the answer, with no recounting.

Complexity

The brute force enumerates paths, and the path count grows faster than any polynomial in the grid side. Breadth-first search visits each cell once, so its time is O(cells).

The brute force stores one route at a time, so its extra space is O(cells) in the worst case. The search stores a visited set and a queue, also O(cells).

from collections import deque

def count_paths(grid):
    rows, cols = len(grid), len(grid[0])
    paths = 0

    def dfs(r, c, seen):
        nonlocal paths
        if (r, c) == (rows - 1, cols - 1):
            paths += 1
            return
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    dfs(nr, nc, seen)
                    seen.discard((nr, nc))

    dfs(0, 0, {(0, 0)})
    return paths

def bfs_visited(grid):
    rows, cols = len(grid), len(grid[0])
    seen = {(0, 0)}
    queue = deque([(0, 0)])
    visited = 0
    while queue:
        r, c = queue.popleft()
        visited += 1
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    queue.append((nr, nc))
    return visited

for n in (2, 3):
    grid = [[0] * n for _ in range(n)]
    print("open", n, "- paths tried:", count_paths(grid), " bfs visited:", bfs_visited(grid))
grid = [[0] * 4 for _ in range(4)]
print("open 4 - bfs visited:", bfs_visited(grid))

The path count pulls away even between sizes 2 and 3. The visited count simply equals the open cell count. Enumeration is the cost, and the level search never pays it.

Edge cases and pitfalls

A one-cell open grid is its own path. Start and target are the same cell, and the answer is one.

Marking cells when they leave the queue is the classic bug. Two neighbours can then enqueue the same cell, and the levels blur.

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
        return -1
    seen = {(0, 0)}
    queue = deque([(0, 0)])
    steps = 1
    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            if (r, c) == (rows - 1, cols - 1):
                return steps
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        if grid[nr][nc] == 0 and (nr, nc) not in seen:
                            seen.add((nr, nc))
                            queue.append((nr, nc))
        steps += 1
    return -1

print("single open cell:", shortest_path([[0]]))
print("single blocked cell:", shortest_path([[1]]))
print("blocked target:", shortest_path([[0, 0], [0, 1]]))
print("single row:", shortest_path([[0, 0, 0]]))

The blocked-target grid returns minus one before any searching. Checking both end cells first keeps that case out of the loop entirely.