DSA Tracker

Visualize

Walls and Gates

Multi-source BFS from every gate at once, one flood-fill wave at a time

time O(rows * cols)space O(rows * cols)

Searching outward from every empty room toward the nearest gate works, but it redoes the same ground once per room. Run the search backwards instead: start from every gate AT THE SAME TIME. Enqueue all of them with distance 0, then expand outward in waves. Because every gate begins the search together, the first wave that reaches any room is guaranteed to have come from the closest gate — a room two steps from one gate and five from another is only ever discovered on wave two, from the near one. One BFS over the whole grid replaces one BFS per room.

Details

Animated on: rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] — fill every empty room (INF = 2147483647) with its distance to the nearest gate (0); walls (-1) stay walls. Drawn as a graph: each non-wall cell is a vertex at its own grid position, each non-wall neighbour pair an edge.

Problem:Walls and GatesMedium

Multi-source BFS from every gate at once, one flood-fill wave at a time

step 1 / 14

4x4 grid, walls excluded

Queue

GateGate

Only the 11 non-wall cells are vertices, joined 4-directionally; walls are not drawn because a wave can never cross one. 2 of them are gates.

Pseudocode
1FUNCTION wallsAndGates(rooms):
2  queue <- ALL (r, c) WHERE rooms[r][c] = 0
3  FOR EACH (r, c) IN queue
4    dist[r][c] <- 0
5  WHILE queue NOT EMPTY
6    (cr, cc) <- REMOVE FIRST FROM queue
7    FOR EACH NEIGHBOUR (nr, nc) OF (cr, cc)
8      IF rooms[nr][nc] = INF
9        rooms[nr][nc] <- dist[cr][cc] + 1
10        dist[nr][nc] <- dist[cr][cc] + 1
11        APPEND (nr, nc) TO queue
12  RETURN rooms

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Only the 11 non-wall cells are vertices, joined 4-directionally; walls are not drawn because a wave can never cross one. 2 of them are gates.
  2. Enqueue all 2 gates at once with distance 0 — this is what makes it multi-source BFS. Searching outward from every empty room instead would redo the same ground many times over.
  3. Pop (0,2) at distance 0. Its unvisited neighbours (1,2)=1, (0,3)=1 get distance 1 — the FIRST time BFS reaches a room is always via the nearest gate, because everything closer was already queued in an earlier wave.
  4. Pop (3,0) at distance 0: neighbour (2,0)=1 joins the frontier. Queue now 3.
  5. Pop (1,2) at distance 1: neighbours (2,2)=2, (1,1)=2 join the frontier. Queue now 4.
  6. Pop (0,3) at distance 1: every neighbour is a wall or already claimed by an earlier wave, so nothing new joins. 3 cells still waiting.
  7. Pop (2,0) at distance 1: neighbour (1,0)=2 joins the frontier. Queue now 3.
  8. Pop (2,2) at distance 2: neighbour (3,2)=3 joins the frontier. Queue now 3.
  9. Pop (1,1) at distance 2: every neighbour is a wall or already claimed by an earlier wave, so nothing new joins. 2 cells still waiting.
  10. Pop (1,0) at distance 2: neighbour (0,0)=3 joins the frontier. Queue now 2.
  11. Pop (3,2) at distance 3: neighbour (3,3)=4 joins the frontier. Queue now 2.
  12. Pop (0,0) at distance 3: every neighbour is a wall or already claimed by an earlier wave, so nothing new joins. 1 cell still waiting.
  13. Pop (3,3) at distance 4: nothing new to claim and the queue is empty — the flood-fill from every gate is done.
  14. Every room reachable from a gate now holds the shortest distance to it. Each vertex's badge is the final answer for that cell.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Walls and Gates in the editorAll Graph problemsBack to roadmap