1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
INF = 2147483647
rows = len(rooms)
if rows == 0:
return
cols = len(rooms[0])
directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}
queue = []
for i in range(rows):
for j in range(cols):
if rooms[i][j] == 0:
queue.append((i, j, 0))
while queue:
i, j, dist = queue.pop(0)
for direction in directions:
new_i = i + direction[0]
new_j = j + direction[1]
if 0 <= new_i < rows and 0 <= new_j < cols and rooms[new_i][new_j] == INF:
rooms[new_i][new_j] = dist + 1
queue.append((new_i, new_j, dist + 1))
|