Walls and Gates

Walls and Gates is the classic problem for learning multi-source BFS — running one breadth-first search from many starting points at once. It looks like a maze, but the trick is to flood outward from every gate simultaneously.

The slow way first

The obvious idea: for each empty room, run a BFS to find the closest gate. That is correct, but you pay a full grid traversal per empty room — roughly O((m·n)²). On a large board that is hopelessly slow.

The question to ask: instead of searching from each room to a gate, why not search from the gates outward? If I expand from all gates at the same time, the first time a wave touches a room, that wave came from the nearest gate — by definition of breadth-first search.

The idea: flood from every gate at once

Seed a single BFS queue with all the gates. Then expand level by level. Every room reached on the first wave is distance 1, the next wave is distance 2, and so on. Because all gates start together, whichever wavefront reaches a room first is the closest gate — so the first value we write is the correct shortest distance, and we never overwrite it.

The key insight: a room is only filled while it is still INF. The first wave to arrive claims it, so it always records the nearest gate and is never touched again.

Walk through it

Step through the animation. Both gates start the wavefront together. The first ring of empty neighbors gets 1, the next ring gets 2, and the single room tucked beside a gate gets 1 directly. When the queue drains, every reachable room holds its shortest distance.

Pseudocode

queue = empty queue
for every cell:
    if cell is a gate (0):
        add its coordinates to queue        # multi-source seed
while queue is not empty:
    (r, c) = pop front of queue
    for each of the 4 neighbors (nr, nc):
        if neighbor is in bounds AND still INF:
            grid[nr][nc] = grid[r][c] + 1     # nearest gate wins
            add (nr, nc) to queue

The Python solution

def walls_and_gates(rooms):
    INF = 2147483647
    R, C = len(rooms), len(rooms[0])
    q = deque()
    for r in range(R):
        for c in range(C):
            if rooms[r][c] == 0:
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

• We seed the queue with every gate first (the nested loop) — that is what makes it multi-source.
• q.popleft() keeps the search breadth-first, so rooms are filled in order of increasing distance.
• The four (dr, dc) offsets are up, down, right, left — the grid neighbors.
• The guard rooms[nr][nc] == INF is doing two jobs: it skips walls (-1) and gates (0), and it skips already-filled rooms — so the first (nearest) wave wins and we never overwrite.
• We set the distance to the current cell plus one, then enqueue the new room to expand later.

Complexity

Because each cell enters the queue at most once, the whole flood is linear in the number of cells. The space is the queue, which in the worst case holds a large fraction of the grid.

When this pattern shows up

Practice