Lesson 21.2 · Breadth-First Search
Grids and Multi-Source BFS
Start BFS from all sources at once by putting them all in the queue at distance 0. Each cell then gets its distance to the nearest source.
12 min
Think of it like this
Several fires starting at the same moment: each spreads one cell per minute, and a cell burns at the time of whichever fire reaches it first. You don't simulate each fire separately.
1.One queue, many starts
Running BFS from each source separately costs O(sources × cells). Instead, enqueue every source first with distance 0 and run a single BFS: O(cells). This answers "how long until everything rots", "distance to the nearest 0" and "farthest water from land".
grid = [[2,1,1],[1,1,0],[0,1,1]]2
1
1
1
1
0
0
1
1
Step 1/5Minute 0: one rotten orange (2). Fresh oranges are 1.
Remember
- All sources enter the queue at distance 0.
- One BFS, O(cells).
- Count fresh cells to detect unreachable ones.
Common mistakes
- One BFS per source.
- Counting the final empty level as an extra minute.