Cross a grid of open and blocked cells from top-left to bottom-right, moving in eight directions. Breadth-first search spreads out one ring at a time, so the first time it reaches the corner is the shortest path: O(n²).
▼The problem
LeetCode 1091 (Medium). Given an n × n binary matrix grid, return the length of the shortest clear path from the top-left cell to the bottom-right cell, or −1 if there is none. A clear path visits only 0 cells, moves between cells that share an edge or a corner (eight directions), and its length is the number of cells it visits, both ends included (so a blocked start or goal means −1).
Examples (LeetCode's): [[0,1],[1,0]] → 2 (one diagonal step); [[0,0,0],[1,1,0],[1,1,0]] → 4 (right, diagonal down, down; walked through the code in scene 5); [[1,0,0],[1,1,0],[1,1,0]] → -1 (the start is blocked).
The solution
def shortestPathBinaryMatrix(grid):
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return -1
q = deque([(0, 0, 1)])
seen = {(0, 0)}
while q:
r, c, d = q.popleft()
if r == n - 1 and c == n - 1:
return d
for nr in range(r - 1, r + 2):
for nc in range(c - 1, c + 2):
if 0 <= nr < n and 0 <= nc < n:
if not grid[nr][nc] and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return -1Transcript
Shortest Path in Binary Matrix. In an n by n grid, zeros are open and ones are blocked. Go from the top-left to the bottom-right, stepping to any of eight neighbors, diagonals too. Return the shortest path's cell count, or minus one if there's none.
In zero one, one zero, one diagonal step works: two cells. In this three by three grid, go right, cut diagonally down, then down: four cells. If the start is blocked, it's minus one.
Depth-first search could try every path. On this five by five grid, its first path takes nine cells, out of forty-eight paths to compare. Bigger grids have exponentially more.
Breadth-first search explores in rings. The start is distance one, its open neighbors two, their new neighbors three. Each ring is one step farther, so the first time the goal leaves the queue, its distance is the shortest.
In code: if either corner is blocked, return minus one. Queue the start at distance one, marking cells seen as they're queued. Pop a cell; if it's the goal, return its distance, else queue each open, unseen neighbor at distance plus one. If the queue empties, return minus one.
Back to the five by five. One at the corner. Two right and below. Three along the top and down the left. Four, then five slips through the gap. Six reaches the goal: the answer is six. The top-right pocket never mattered.
Each cell is queued once and checks eight neighbors: n squared time, and n squared space for the queue and seen marks.
Spread ring by ring, mark cells as you queue them, stop at the goal. That's Shortest Path in Binary Matrix.