AlgoViz
HomeGraphs

Shortest Distance in a Binary Maze

Hard

BFS across open cells

Problem

Return the shortest path length from source to destination in a binary maze (1 = open).

In simple words

BFS from the start over open cells; the first time you pop the destination is the shortest distance.

The idea

Every step costs one, so BFS from the source over walkable cells finds the shortest route. The level at which the destination is dequeued is the answer.

The trick

  • Mark cells visited as you enqueue, not as you dequeue, or duplicates pile up.
  • Return -1 if the queue empties without reaching the destination.
R
F
F
F
F
·
·
F
F
minute0
fresh6

Step 1 of 6. Every rotten orange (R) rots its fresh (F) neighbours each minute — a multi-source BFS. minute 0, fresh 6.

1/6
Optimal
timeO(rows·cols)spaceO(rows·cols)

All sources start at minute 0.

1// enqueue all rotten cells; BFS by layers,2// converting fresh neighbors, counting minutes.3while (q.length && fresh > 0) {4  minutes++;5  for (let n = q.length; n > 0; n--) spread(q.shift());6}7return fresh === 0 ? minutes : -1;

Input

grid
3 × 3

Memory

minute
0
fresh
6

Output

minute
0
fresh
6
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
grid=[[1,1,1],[1,0,1],[1,1,1]], src=[0,0], dst=[2,2]
Output:
4
Explanation:
Shortest open path is 4 steps.

Example 2

Input:
grid=[[1,1],[1,1]], src=[0,0], dst=[1,1]
Output:
2
Explanation:
Two steps to the corner.

Example 3

Input:
grid=[[1,0],[0,1]], src=[0,0], dst=[1,1]
Output:
-1
Explanation:
Blocked diagonally → -1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.