Shortest Path in Binary Matrix

Medium#1091grid

A square grid of 0s and 1s: 0 is open, 1 is blocked. Walk from the top-left cell to the bottom-right one through open cells, stepping to any of the 8 cells around, diagonals too. Return the length of the shortest such path in cells, start and end included, or -1 if there is none. Our example: 0011 / 1010 / 1101 / 1000 — the answer is 4.

1091 Shortest Path in Binary MatrixWalkthrough · 1×

Example: find the shortest path in cells through 0011 / 1010 / 1101 / 1000, moving in 8 directions.

01230123########queuefront on the left—
open, not reachedin the queuecurrent cellneighbour being addeddoneblocked

Both corners, (0, 0) and (3, 3), are open

01/54
restart · back · play · step
Speed
1function shortestPathBinaryMatrix(grid):
2 if grid[0][0] or the last cell is blocked:
3 return -1
4 dist = table filled with none
5 dist[0][0] = 1 // the path counts cells
6 queue = [(0, 0)]
7 while queue is not empty:
8 (r, c) = queue.popFront()
9 if (r, c) is the last cell:
10 return dist[r][c]
11 for (nr, nc) in 8 open neighbours, no dist:
12 dist[nr][nc] = dist[r][c] + 1
13 queue.pushBack((nr, nc))
14 return -1
state
dist
–
queue
–
r
–
c
–
nr
–
nc
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every step costs the same, so cells leave the queue in order of path length: the first time the last cell comes out, its length is the shortest.
  2. A cell gets its dist when it is first queued and is never queued again, so nothing is counted twice.
  3. A diagonal counts as one step, so a gap between two walls that touch at a corner is a way through.

Complexity

Time O(n²): each of the n² cells is queued at most once and looks at 8 neighbours. Memory O(n²) for dist and the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.