Card 05/ 08
Grid Traversal Example: How Far Every Desk Is From Its Nearest Exit
One search per desk repeats the same work many times; starting one search from every exit at once gives each desk its nearest exit in a single pass.
A breadth-first search can start from many cells at once, and then every cell's distance is its distance to the nearest of them. An office floor plan marks exits with E, pillars with # and desks with ., and the fire officer wants, for every desk, the fewest moves to an exit, moving up, down, left or right. The question asks about every desk, which reads as one search per desk; it is one search with two starts.
E . . # . .
. # . . . E
. # . # . .
. . . . # .Which desk is farthest from any exit?
The desk at (3, 3), 6 moves from either exit. Pillars above and to the right of it leave one way in, from (3, 2).
Every exit enters the queue at distance 0 before the search starts. Each wave is then one move farther from the nearest exit, whichever exit that is, and a desk is reached first from the exit nearest to it, by the invariant of breadth-first search. Nothing else in the template changes. The run prints each cell's distance to its nearest exit.
from collections import deque
DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))
floor = ["E..#..", ".#...E", ".#.#..", "....#."]
rows, cols = len(floor), len(floor[0])
distance = [[-1] * cols for _ in range(rows)]
queue: deque[tuple[int, int]] = deque()
for row in range(rows):
for col in range(cols):
if floor[row][col] == "E":
distance[row][col] = 0
queue.append((row, col))
while queue:
row, col = queue.popleft()
for d_row, d_col in DIRECTIONS:
r, c = row + d_row, col + d_col
if 0 <= r < rows and 0 <= c < cols and floor[r][c] != "#" and distance[r][c] == -1:
distance[r][c] = distance[row][col] + 1
queue.append((r, c))
for r, line in enumerate(floor):
print(" ".join("#" if cell == "#" else str(distance[r][c]) for c, cell in enumerate(line)))
desks = [(r, c) for r in range(rows) for c in range(cols) if floor[r][c] == "."]
farthest = max(desks, key=lambda cell: distance[cell[0]][cell[1]])
print(f"desks: {len(desks)}, exits: {sum(line.count('E') for line in floor)}")
print(f"farthest desk: {farthest}, {distance[farthest[0]][farthest[1]]} moves from the nearest exit")0 1 2 # 2 1
1 # 3 2 1 0
2 # 4 # 2 1
3 4 5 6 # 2
desks: 17, exits: 2
farthest desk: (3, 3), 6 moves from the nearest exitThe floor has 17 desks and 2 exits, and the three ways to answer the question differ in how many searches they run.
| Approach | Searches | Cost |
|---|---|---|
| A search from each desk until it meets an exit | One per desk, 17 here | O((R · C)²) |
| A search from each exit, then the smallest distance per desk | One per exit, 2 here | O(k · R · C) for k exits |
| One search from every exit at once | 1 | O(R · C) |
With two exits the second approach costs only twice the third, but a floor with fifty exits would run fifty searches, while the many-source search still visits each cell once. The same move answers how long a fire takes to reach every room when it starts in several places, and how far every house is from its nearest shop.
← → move through sections and cards