Graphs
Starting from everywhere at once
Breadth-first search measures distance. Seeding the queue with many starts measures distance to the nearest one.
Key idea
Why breadth-first measures distance
Breadth-first search reaches everything at distance one, then everything at distance two, and so on. So the first time it arrives at a node, it arrives by a shortest path.
That is only true when every edge costs the same. Weighted edges break it, and fixing that is Unit 13. For unweighted graphs and grids, breadth-first search is the shortest-path algorithm and nothing more elaborate is needed.
The wasteful version
To find each cell's distance to the nearest source, the obvious approach runs a separate search from every cell. That is one full traversal per cell.
Turn it around, as in Unit 2's container problem and Unit 11's grid search: instead of asking each cell how far the nearest source is, let all the sources spread outward together.
Why it works
Seed the queue with every source
Put all the sources into the queue before the loop starts, all at distance zero. The search then expands them in lockstep, and the first arrival at any cell is by the shortest path from whichever source is nearest.
The correctness argument is the same as for a single source. Everything in the queue at any moment is at the current distance or one more, so arrivals happen in non-decreasing distance order regardless of how many places the search began.
All of that is decided before the loop runs a single step. Here is the state it starts from.
Tip
The distance array is the visited set
A separate visited set would be redundant. A cell with distance still at -1 has not been reached, so the distance array answers both questions at once.
Merging the two removes a chance for them to disagree, which is a small but real class of bug. The blocked cell stays at -1 forever, which correctly reads as unreachable.
Key idea
Counting rounds instead of per-node distances
Some problems want how many rounds until everything is reached rather than each node's distance. That is the level-batching loop from Unit 8: record the queue length, process exactly that many, and increment a counter per round.
Both forms are the same search. Use per-node distances when the answer is about individual nodes and round counting when the answer is a single number about the whole process.
Edge cases
Check what was left behind
When the question is how long until everything is reached, something unreachable makes the answer impossible rather than large. After the search, scan for anything still unvisited and report the failure value.
Forgetting that scan gives a plausible number on an input that has no answer, which is worse than an obvious crash. Both problems below have this case and both grade it.
Cost
Cost
Every cell enters the queue at most once and is examined once per neighbor, so O(rows times cols) time and the same space. Seeding with many sources does not change that; it only changes where the wavefront starts.
Compare against the naive per-cell search, which is that whole cost multiplied by the number of cells. Stating both is the point of the lesson.
Trace the wavefront
Run the multi-source search on a 1 by 5 row S . . . S with no blocked cells. Give the distance assigned to each position, left to right.
This activity type is not wired up yet.
Walls And Gates
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Rotting Oranges
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.