139. Walls and Gates

Why this mechanism works

All gates are simultaneous BFS sources. The INF marker means both empty room and undiscovered distance. Writing a finite distance at enqueue time prevents duplicate discovery and leaves unreachable rooms visibly distinct from distance-zero gates.

State and boundaries

queue holds discovered rooms or gates. A finite nonnegative grid entry is its final nearest-gate distance; INF remains undiscovered.

Protocol

1. Enqueue every gate.
2. Pop the next known-distance cell.
3. For each neighboring INF room, assign current distance+1.
4. Enqueue it immediately.
5. Return the mutated grid after exhaustion.

Visualization

0 INF -1
INF INF INF
becomes
0 1 -1
1 2 3

Python implementation

from collections import deque

INF = 2**31 - 1

def walls_and_gates(rooms):
    rows = len(rooms)
    cols = len(rooms[0]) if rows else 0
    queue = deque((r, c) for r in range(rows) for c in range(cols)
                  if rooms[r][c] == 0)
    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
                queue.append((nr, nc))
    return rooms

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L6 walls_and_gates: rows = len(rooms)
rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]; rows=2

L7 walls_and_gates: cols = len(rooms[0]) if rows else 0
rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]; rows=2; cols=3

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=0; c=0; cols=3; rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=0; c=1; cols=3; rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=0; c=2; cols=3; rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=1; c=0; cols=3; rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=1; c=1; cols=3; rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=1; c=2; cols=3; rooms=[[0, 2147483647, -1], [2147483647, 2147483647, 2147483647]]

... 50 intermediate state changes omitted ...

L12 walls_and_gates: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
rooms=[[0, 1, -1], [1, 2, 3]]; rows=2; cols=3; queue=deque([]); r=1; c=2; dr=0; dc=1; nr=0; nc=2

L13 walls_and_gates: nr, nc = r + dr, c + dc
rooms=[[0, 1, -1], [1, 2, 3]]; rows=2; cols=3; queue=deque([]); r=1; c=2; dr=0; dc=1; nr=1; nc=3

L12 walls_and_gates: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
rooms=[[0, 1, -1], [1, 2, 3]]; rows=2; cols=3; queue=deque([]); r=1; c=2; dr=0; dc=-1; nr=1; nc=3

L13 walls_and_gates: nr, nc = r + dr, c + dc
rooms=[[0, 1, -1], [1, 2, 3]]; rows=2; cols=3; queue=deque([]); r=1; c=2; dr=0; dc=-1; nr=1; nc=1

L6 walls_and_gates: rows = len(rooms)
rooms=[[2147483647, -1, 0]]; rows=1

L7 walls_and_gates: cols = len(rooms[0]) if rows else 0
rooms=[[2147483647, -1, 0]]; rows=1; cols=3

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=0; c=0; cols=3; rooms=[[2147483647, -1, 0]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=0; c=1; cols=3; rooms=[[2147483647, -1, 0]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=0; c=2; cols=3; rooms=[[2147483647, -1, 0]]

L8 <genexpr>: queue = deque((r, c) for r in range(rows) for c in range(cols)
.0=range_iterator; r=0; c=2; cols=3; rooms=[[2147483647, -1, 0]]

L8 walls_and_gates: queue = deque((r, c) for r in range(rows) for c in range(cols)
rooms=[[2147483647, -1, 0]]; rows=1; cols=3; queue=deque([(0, 2)])

L11 walls_and_gates: r, c = queue.popleft()
rooms=[[2147483647, -1, 0]]; rows=1; cols=3; queue=deque([]); r=0; c=2

... 4 intermediate state changes omitted ...

L12 walls_and_gates: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
rooms=[[2147483647, -1, 0]]; rows=1; cols=3; queue=deque([]); r=0; c=2; dr=0; dc=1; nr=-1; nc=2

L13 walls_and_gates: nr, nc = r + dr, c + dc
rooms=[[2147483647, -1, 0]]; rows=1; cols=3; queue=deque([]); r=0; c=2; dr=0; dc=1; nr=0; nc=3

L12 walls_and_gates: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
rooms=[[2147483647, -1, 0]]; rows=1; cols=3; queue=deque([]); r=0; c=2; dr=0; dc=-1; nr=0; nc=3

L13 walls_and_gates: nr, nc = r + dr, c + dc
rooms=[[2147483647, -1, 0]]; rows=1; cols=3; queue=deque([]); r=0; c=2; dr=0; dc=-1; nr=0; nc=1

Why the solution is correct

BFS layer order guarantees the first path reaching an INF room is shortest from any gate. Walls are never traversed and already assigned cells need no later improvement under unit edge costs. Remaining INF cells have no gate path.

Time and space

O(R*C) time and O(R*C) queue space; distances reuse the input matrix.

Common mistakes

Using zero as an unvisited marker overwrites gates. Treating walls as candidates lets paths cross forbidden cells.

Reasoning card

Transfer exercise

Also record which gate serves each room, defining a deterministic tie rule for equal-distance gates.