Walls and Gates — The Fire Drill Map

Boss 4: The Fire Drill Map

Boss 3 cloned a graph by walking it, DFS diving down one corridor at a time, backtracking when it hit a dead end. This boss retires the dive and installs the other fundamental walk: BFS, the ring-by-ring sweep that visits everything at distance 1, then everything at distance 2, and so on. Then it supercharges it with the twist that makes it a boss: many starting points at once. One queue, all sources seeded together, and every cell in the grid learns its true nearest distance in a single pass.

The story

You're the safety officer for a small office floor. Fire code says every room gets a sign: nearest exit, N steps. The floor plan is a grid, exits are 0, walls are -1, and empty rooms start as INF (a placeholder meaning "no sign yet"):

INF  -1    0  INF
INF  INF  INF  -1
INF  -1   INF  -1
 0   -1   INF  INF

Two exits: top row and bottom-left corner. Instead of pacing out each room, you stand at both exits and let the count ripple outward:

seed: both gates in the queue          (0,2) and (3,0), distance 0

ring 1:  (0,3)=1  (1,2)=1              one step from the top gate
         (2,0)=1                       one step from the bottom gate
ring 2:  (1,1)=2  (2,2)=2  (1,0)=2     spreading from ring 1
ring 3:  (0,0)=3  (3,2)=3
ring 4:  (3,3)=4                       queue empty, done

3   -1   0   1
2    2   1  -1
1   -1   2  -1
0   -1   3   4

Notice room (1,0). The top gate could reach it in 3 steps, the bottom gate in 2. It got stamped 2, and nobody compared anything. The bottom gate's ripple simply arrived first, and in BFS, first arrival is always the shortest path. That's the whole trick.

The problem, dressed up properly

You are given an m x n grid rooms initialized with three possible values: -1 for a wall, 0 for a gate, and INF (2147483647) for an empty room. Fill each empty room with the distance to its nearest gate. If a room cannot reach any gate, leave it as INF.

LeetCode 286. It's a premium problem there, but the exact same puzzle is free on NeetCode under the name "Islands and Treasure".

The naive attempt

Run a fresh search from every room until it finds a gate:

from collections import deque
 
def walls_and_gates(rooms):
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == INF:
                rooms[r][c] = bfs_from(rooms, r, c)   # O(mn) each time

Each search can sweep the whole grid, and there are up to m*n rooms: O((mn)²). Running one BFS per gate and keeping the minimum has the same problem, k gates times a full-grid sweep each, plus a min-merge. Both versions re-walk the same hallways over and over. The floor doesn't change between searches, so all that repetition is pure waste.

The weapon: multi-source BFS

First, BFS itself, since bosses 1 through 3 leaned on DFS. BFS uses a queue (first in, first out). You seed it with starting cells, then loop: pop the front, look at its 4 neighbors, push any unvisited ones to the back. Because the queue serves cells in the order they were discovered, the walk proceeds in rings: every cell at distance 1 comes out before any cell at distance 2. A visited check stops cells from entering twice.

The boss move: don't pick one start. Seed the queue with every gate at once, all at distance 0. The rings now grow from all gates simultaneously, like ripples from several stones tossed in a pond. Wherever two ripples would overlap, the nearer gate's ripple got there first, so each room is stamped exactly once, with its true nearest distance.

from collections import deque
 
def walls_and_gates(rooms: list[list[int]]) -> None:
    INF = 2147483647
    rows, cols = len(rooms), len(rooms[0])
    queue = deque()
 
    for r in range(rows):                     # seed: every gate, distance 0
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))
 
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1   # first arrival wins
                queue.append((nr, nc))

No separate visited set needed. A room stops being INF the moment it's stamped, so the == INF check does triple duty: skips walls, skips gates, skips anything already reached. The grid is its own bookkeeping.

Watching it work

The story's floor plan, with the queue's actual contents:

queue: (0,2) (3,0)                        both gates, distance 0
pop (0,2): stamp (0,3)=1, (1,2)=1         queue: (3,0) (0,3) (1,2)
pop (3,0): stamp (2,0)=1                  queue: (0,3) (1,2) (2,0)
pop (0,3): nothing new (wall, stamped)
pop (1,2): stamp (1,1)=2, (2,2)=2
pop (2,0): stamp (1,0)=2
pop (1,1), (2,2), (1,0): stamp (0,0)=3, (3,2)=3
pop (0,0), (3,2): stamp (3,3)=4
pop (3,3): nothing new, queue empty ✓

Distance-1 cells all left the queue before any distance-2 cell entered play. The rings never interleave, which is exactly why the first stamp is always the smallest possible.

Gotchas

1. Using a stack instead of a queue. Swap popleft() for pop() and you've silently built DFS. It still visits everything, but stamps arrive in dive order, not ring order, so the distances are garbage. BFS's shortest-path guarantee lives entirely in the FIFO queue.

2. Marking visited at pop time instead of push time. Stamp the room when you push it, not when it comes out. Delay the mark and the same room gets pushed by several neighbors before its turn comes, bloating the queue and overwriting good distances.

3. Seeding gates one at a time. Running a full BFS per gate and taking the minimum is the naive solution wearing a BFS costume. The magic is one shared queue, all gates in it before the loop starts.

4. Forgetting walls exist. The == INF check quietly handles them, walls are -1, never INF. But if you track visited in a separate set and check that instead, you must remember to also skip walls, or the flood walks through concrete.

5. Stamping the popped cell instead of the neighbor. The popped cell already knows its distance. You're writing rooms[nr][nc] = rooms[r][c] + 1, new cell, old value plus one. Mixing up which side gets written is a classic 2 a.m. bug.

Complexity

Every cell enters the queue at most once and checks 4 neighbors when popped.

Time: O(mn). Space: O(mn).

Boss down. XP gained.

The safety officer prints one map, every sign truthful, and never once walked a hallway twice. The inspector signs off before lunch.

What you walked away with:

• BFS proper: a FIFO queue, ring-by-ring expansion, visited marked at push time
• Multi-source seeding: many starts, one queue, and first arrival is provably nearest
• The grid as its own visited set, INF means "not yet reached"
• "Nearest X for every cell" means flood from the X's, not from the askers

Next up: Boss 5 — The Fruit Stall Mold. Same multi-source flood, but now the rings are the clock: each BFS level is one hour of mold spreading through a crate of oranges, and you have to notice when some fruit can never be reached at all.