Starting from everywhere at once

Breadth-first search measures distance. Seeding the queue with many starts measures distance to the nearest one.

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.

1row = ["S", ".", ".", ".", "S"]2 3queue = [(0, c) for c, cell in enumerate(row) if cell == "S"]4distance = [0 if cell == "S" else -1 for cell in row]5 6print("seeded queue:", queue)7print("distances before the loop:", distance)

Two sources, both at zero, both already queued. The loop that follows is an ordinary breadth-first search.

Trace it· 8 min

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.

position	distance
0
1
2
3
4

Problem· 25 min

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.

Problem· 25 min

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.

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.

1row = ["S", ".", ".", ".", "S"]2 3queue = [(0, c) for c, cell in enumerate(row) if cell == "S"]4distance = [0 if cell == "S" else -1 for cell in row]5 6print("seeded queue:", queue)7print("distances before the loop:", distance)

position

distance