286. Walls and Gates

Fill each empty room (2147483647) of a grid with the distance to its nearest gate (0). Walls (-1) block movement; unreachable rooms stay 2147483647. Modify rooms in place.

Start a BFS from all gates at once. BFS reaches each room first along a shortest path, so each empty room is written exactly once with its final distance.

1function wallsAndGates(rooms: number[][]): void {
2  const m = rooms.length, n = rooms[0].length, queue: number[][] = [];
3  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (rooms[r][c] === 0) queue.push([r, c]);
4  while (queue.length) {
5    const [r, c] = queue.shift()!;
6    for (const [x, y] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]])
7      if (x >= 0 && y >= 0 && x < m && y < n && rooms[x][y] === 2147483647) {
8        rooms[x][y] = rooms[r][c] + 1; queue.push([x, y]);
9      }
10  }
11}

rooms (▇ wall, 0 gate, ∞ empty)

∞	▇	0	∞
∞	∞	∞	▇
∞	▇	∞	▇
0	▇	∞	∞

queue

(0,2)

(3,0)

Start from all 2 gates.

1 / 0

Space: play/pause · ←/→: step