137. Shortest Binary-Matrix Path

Why this mechanism works

Every move has equal cost, so BFS first reaches each cell by a shortest route. Store distance in cells, starting at one for the initial cell. Mark on enqueue to avoid duplicate frontier entries. Blocked endpoints can be rejected before traversal.

State and boundaries

queue contains discovered open cells with their shortest cell-count distance. seen prevents rediscovery.

Protocol

1. Reject empty or blocked endpoints.
2. Enqueue the start at distance one.
3. Pop the next BFS cell.
4. Return its distance when it is the destination.
5. Enqueue unseen open neighbors at distance+1.
6. Return -1 if exhausted.

Visualization

0 1
1 0
diagonal path visits two open cells
answer 2, despite blocked side neighbors

Python implementation

from collections import deque

def shortest_binary_path(grid):
    if not grid or not grid[0] or grid[0][0] != 0 or grid[-1][-1] != 0:
        return -1
    rows, cols = len(grid), len(grid[0])
    queue = deque([(0, 0, 1)])
    seen = {(0, 0)}
    while queue:
        r, c, distance = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return distance
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if ((dr or dc) and 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, distance + 1))
    return -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 shortest_binary_path: if not grid or not grid[0] or grid[0][0] != 0 or grid[-1][-1] != 0:
grid=[[0, 1], [1, 0]]

L6 shortest_binary_path: rows, cols = len(grid), len(grid[0])
grid=[[0, 1], [1, 0]]; rows=2; cols=2

L7 shortest_binary_path: queue = deque([(0, 0, 1)])
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([(0, 0, 1)])

L8 shortest_binary_path: seen = {(0, 0)}
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([(0, 0, 1)]); seen={(0, 0)}

L10 shortest_binary_path: r, c, distance = queue.popleft()
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([]); seen={(0, 0)}; r=0; c=0; distance=1

L13 shortest_binary_path: for dr in (-1, 0, 1):
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([]); seen={(0, 0)}; r=0; c=0; distance=1; dr=-1

L14 shortest_binary_path: for dc in (-1, 0, 1):
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([]); seen={(0, 0)}; r=0; c=0; distance=1; dr=-1; dc=-1

L15 shortest_binary_path: nr, nc = r + dr, c + dc
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([]); seen={(0, 0)}; r=0; c=0; distance=1; dr=-1; dc=-1; nr=-1; nc=-1

... 17 intermediate state changes omitted ...

L15 shortest_binary_path: nr, nc = r + dr, c + dc
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([]); seen={(0, 0)}; r=0; c=0; distance=1; dr=1; dc=1; nr=1; nc=1

L18 shortest_binary_path: seen.add((nr, nc))
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([]); seen={(0, 0), (1, 1)}; r=0; c=0; distance=1; dr=1; dc=1; nr=1; nc=1

L19 shortest_binary_path: queue.append((nr, nc, distance + 1))
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([(1, 1, 2)]); seen={(0, 0), (1, 1)}; r=0; c=0; distance=1; dr=1; dc=1; nr=1; nc=1

L10 shortest_binary_path: r, c, distance = queue.popleft()
grid=[[0, 1], [1, 0]]; rows=2; cols=2; queue=deque([]); seen={(0, 0), (1, 1)}; r=1; c=1; distance=2; dr=1; dc=1; nr=1; nc=1

L4 shortest_binary_path: if not grid or not grid[0] or grid[0][0] != 0 or grid[-1][-1] != 0:
grid=[[0]]

L6 shortest_binary_path: rows, cols = len(grid), len(grid[0])
grid=[[0]]; rows=1; cols=1

L7 shortest_binary_path: queue = deque([(0, 0, 1)])
grid=[[0]]; rows=1; cols=1; queue=deque([(0, 0, 1)])

L8 shortest_binary_path: seen = {(0, 0)}
grid=[[0]]; rows=1; cols=1; queue=deque([(0, 0, 1)]); seen={(0, 0)}

L10 shortest_binary_path: r, c, distance = queue.popleft()
grid=[[0]]; rows=1; cols=1; queue=deque([]); seen={(0, 0)}; r=0; c=0; distance=1

Why the solution is correct

FIFO order expands all paths of one move count before longer paths. Therefore a cell's first discovery has minimum distance, and the first destination removal yields the shortest path. Exhaustion means every reachable open cell was considered without reaching the destination.

Time and space

O(R*C) time and O(R*C) auxiliary space; eight neighbors per cell is a constant factor.

Common mistakes

Starting distance at zero reports edges rather than cells. Using only four neighbors rejects legal diagonal paths under this contract.

Reasoning card

Transfer exercise

Store one predecessor per discovered cell to return a shortest path, not just its length.