286. Walls and Gates
BFS, Array, Matrix, AMateList ·Problem Statement
link: LeetCode.cn LeetCode You are given an m x n grid rooms initialized with these three possible values.
-1 A wall or an obstacle. 0 A gate. INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
Example:
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: m == rooms.length n == rooms[i].length 1 <= m, n <= 250 rooms[i][j] is -1, 0, or 231 - 1.
Solution Approach
The solution uses a BFS approach to propagate distances from each gate to its nearest empty rooms, updating each room with the shortest distance to a gate.
Algorithm
- Initialization: Iterate through the grid to find all gates (cells with value 0) and add their coordinates to the stack.
- BFS Propagation: Use a BFS-like traversal with a stack to process each gate and update the distances of its neighboring cells, adding newly updated cells to a temporary list (nex) for the next iteration.
- Update Distances: After processing all cells in the current level of BFS, increment the distance step and replace the stack with the temporary list (nex) for the next level, continuing until all reachable cells are updated.
Time Complexity
O(m * n)
Space Complexity
O(m * n)
Implement
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
directions = [(1,0),(0,1),(-1,0),(0,-1)]
null = 2147483647
m, n = len(rooms), len(rooms[0])
stack = []
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
stack.append([i, j])
step = 1
while stack:
nex = []
for i, j in stack:
for dx,dy in directions:
cx, cy = i + dx, j + dy
if 0 <= cx < m and 0 <= cy < n and rooms[cx][cy] == null:
nex.append([cx, cy])
rooms[cx][cy] = step
step += 1
stack = nex
return