The problem
Each cell of a grid is −1 (a wall), 0 (a gate), or 2147483647 (an empty room; the largest 32-bit integer stands for “infinity”).
Fill each empty room with the number of steps (up, down, left, right, never through a wall) to its nearest gate. A room no gate can reach keeps 2147483647. Change the grid in place.
Examples
- Input
rooms = [ [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]]
- Input
rooms = [[-1]]
- Output
[[-1]]
Constraints
- 1 ≤ m, n ≤ 250
- Each cell is −1, 0 or 2³¹ − 1.
The idea
Searching from every room to find its nearest gate repeats work. Instead search from all the gates at once, breadth-first, like the rot in Rotting Oranges.
Breadth-first search reaches cells in order of distance. So the first time a room is reached, it is from its nearest gate, by the shortest route: write down that distance and never touch the room again. A room still at infinity when the search ends has no route to any gate.
- Time
- O(m · n)
- Space
- O(m · n) — the queue
Solution · every language run against every case
class Solution: def wallsAndGates(self, rooms: List[List[int]]) -> None: INF = 2147483647 # an empty room not yet reached rows, cols = len(rooms), len(rooms[0]) # Breadth-first from every gate at once: a room is first reached from its nearest gate. queue = deque((r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0) while queue: i, j = queue.popleft() for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)): if 0 <= x < rows and 0 <= y < cols and rooms[x][y] == INF: rooms[x][y] = rooms[i][j] + 1 queue.append((x, y))