Description
Fill each empty room with its shortest distance to a gate, moving in four directions through rooms. Walls are -1, gates are 0, and empty rooms start at 2147483647. Unreachable rooms keep that value; modify the grid in place.
Solution
from collections import deque
def walls_and_gates(rooms):
rows, cols = len(rooms), len(rooms[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 x, y in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= x < rows and 0 <= y < cols and rooms[x][y] == 2147483647:
rooms[x][y] = rooms[r][c] + 1
queue.append((x, y))Examples
Example 1
- Input
[[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]]- Output
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
Each room receives its nearest gate distance.
Example 2
- Input
[[[2147483647]]]- Output
[[2147483647]]
Without a gate the room stays unreachable.
Example 3
- Input
[[[0,2147483647]]]- Output
[[0,1]]
The adjacent room is one step away.
Approach
Enqueue all gates and run one multi-source BFS. On first reaching an empty room, set its distance to the current cell's distance plus one. BFS guarantees the first assigned distance is shortest.
Time & space
O(rc) time and O(rc) auxiliary space, where r and c are room-grid dimensions.