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 1:
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]]
- code best, remove visited, as we just check those room with Max value
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
m = len(rooms)
n = len(rooms[0])
q = deque()
for row in range(m):
for col in range(n):
if rooms[row][col] == 0:
q.append((row, col))
direction = [(-1,0),(1,0),(0,-1),(0,1)]
while q:
x, y = q.popleft()
for dx, dy in direction:
next_x, next_y = x + dx, y + dy
if m > next_x >= 0 and n > next_y >= 0 and rooms[next_x][next_y] == 2 ** 31 - 1:
rooms[next_x][next_y] = rooms[x][y] + 1
q.append((next_x, next_y))