Multi-source BFS for the nearest exit on a grid
Find the nearest exit for every room with one breadth-first search. Trace where two waves meet, handle unreachable rooms, and count the work in C#.
A floor plan has two exits. You need to write the number of steps to the nearest exit on every open square. Starting a search in each room gives the right answer. It also means the room next door searches much of the same floor again. Turn the question around. If both exits send a wave through the building at the same time, which wave reaches each room first?
Take this little floor. E is an exit, . is an open square and # is a wall. A step costs one and moves horizontally or vertically. Doors work in both directions. An exit has distance zero because someone standing there has already arrived.
E...E
.#.#.
.....The room in the middle of the top row is two steps from either exit. The bottom middle room can go through the center, around the left side, or around the right side. It needs four steps whichever route it chooses. A complete solution has to get both rooms right without making a special rule about ties.
-
Top row
- 0
- 1
- 2
- 1
- 0
Both exits start at zero.
-
Middle row
- 1
- #
- 3
- #
- 1
The center room can go straight up to the top corridor.
-
Bottom row
- 2
- 3
- 4
- 3
- 2
Four is the largest distance on this floor.
An ordinary breadth-first search (BFS) uses a first-in, first-out queue. It starts at one point, visits that point's neighbors, then their neighbors. To give two exits equal standing, put both in the queue before the first removal. Everything else in the traversal works as it does for a single starting point. With ten exits, put all ten in the queue.
Watch the top corridor. The left exit claims the square immediately to its right at distance one. The right exit claims the square immediately to its left at distance one. Eventually one of those squares claims the middle at distance two. When the other tries, the middle already has a distance. Both candidates offer two, so keeping the first value is correct. Reversing the order of the exits might select a different walking route. The distance printed on the floor stays the same.
When a room first joins the queue, its distance to the nearest exit is final. Every shorter walk would have reached it from a room that the queue processed earlier.
To see the ordering behind that claim, imagine freezing the queue just before processing the first entry at distance two. All rooms at distance zero or one have already been removed. Any room reachable in at most two steps has therefore been discovered, since its predecessor on that walk was at most one step away. Removing the distance-two rooms can only add rooms at distance three. Induction carries the argument across the floor.
This C# method takes a rectangular floor with the three symbols above and returns a grid of distances. An entry of -1 means the algorithm found no route there. Walls also keep -1, so a caller that displays the map can distinguish them using the original floor. The input stays available for that purpose. An empty floor produces an empty result.
static int[,] DistancesToExits(string[] floor)
{
int rows = floor.Length;
int columns = rows == 0 ? 0 : floor[0].Length;
var distance = new int[rows, columns];
var queue = new Queue<(int Row, int Column)>();
(int Row, int Column)[] steps = [(-1, 0), (1, 0), (0, -1), (0, 1)];
for (int row = 0; row < rows; row++)
{
for (int column = 0; column < columns; column++)
{
distance[row, column] = -1;
if (floor[row][column] == 'E')
{
distance[row, column] = 0;
queue.Enqueue((row, column));
}
}
}
while (queue.TryDequeue(out var room))
{
foreach (var step in steps)
{
int row = room.Row + step.Row;
int column = room.Column + step.Column;
if (row < 0 || row >= rows || column < 0 || column >= columns)
continue;
if (floor[row][column] == '#' || distance[row, column] != -1)
continue;
distance[row, column] = distance[room.Row, room.Column] + 1;
queue.Enqueue((row, column));
}
}
return distance;
}The placement of the assignment matters. In the top corridor two parents can discover the same middle square. If a room is marked only when removed from the queue, both parents can schedule it. A check on removal could still produce correct distances, but duplicate entries complicate the work bound. Storing the distance when you enqueue lets a single value mean both "already scheduled" and "this many steps away."
Picture a one-cell-wide corridor of n squares with one exit at the left. A simulation that scans all n squares for each new wave runs n - 1 waves. A thousand squares require almost a million square inspections. This shape also catches a subtle correctness bug in a simulation. Update a room in place, then keep scanning to its right, and the freshly updated room might update its own neighbor in the very same minute. A whole corridor can appear to fill in one tick. A snapshot or a separate collection for the next wave keeps the minutes distinct. An in-place scan can also stamp each room with its arrival minute and expand only from rooms stamped in the previous minute.
The queue examines at most four neighbors per removed square. Each accessible square joins once. Including the initial scan, the running time is linear in the total number of squares, even if the exit count grows with the size of the building. The output occupies one integer per square. The queue can also need that much space when a floor has many starting points. All exits begin there together. Shortening the corridors changes the distances and queue shape while preserving this upper bound. This is the kind of shape change to try when reading an algorithm's performance results.
First, seal off a room. On the single row E.#., the four distances are 0, 1, -1, -1. The last room is open and unreachable. Taking the largest nonnegative entry would give one, which answers how far the wave traveled. If the requirement says every room must reach an exit, that same map represents a failure. Keep the unreachable marker long enough for the caller to make that distinction. On a floor with no exits, the initial queue is empty and every room retains its marker.
Next, make some doors one-way. The route a person takes toward an exit must be a legal walk. A wave sent out from an exit consequently needs the reverse of each allowed step. Otherwise the algorithm finds rooms the exit can reach. An exit-only turnstile is a useful tiny fixture. A room with a directed edge into the exit should receive distance one even though the exit has no outgoing edge.
Finally, give the stairwell a cost of five and the corridor a cost of one. A path with fewer edges can now take longer. First discovery in a FIFO queue loses its guarantee. For nonnegative travel costs, seed a priority queue with each exit at cost zero and relax cheaper routes using Dijkstra's priority queue.
The Rotting Oranges kata in C# coding challenges asks for one number from this distance map. Each initially rotten orange starts at minute zero. The answer is the greatest arrival time among the initially fresh oranges, with zero for an empty set and -1 when any fresh orange is unreachable. Those three outcomes make a compact check on what the last wave actually tells you.
Practice what you just read
- Open in the editor: Rotting Oranges
Algorithm Medium Free, no account needed
Rotting Oranges
How many minutes until the rot spreads everywhere?
More like this: C# coding challenges →