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 2^{31}  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:
_ # G _ 3 # 0 1
_ _ _ # 2 2 1 #
_ # _ # 1 # 2 #
G # _ _ 0 # 3 $
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]]
Example 2:
Input: rooms = [[1]]
Output: [[1]]
Constraints:
m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j]
is 1
, 0
, or 2^{31}  1
.
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
27
28
29
30
31
32
33
34
35
36
37

from collections import deque
class Solution:
INF = 2147483647
def wallsAndGates(self, rooms: List[List[int]]) > None:
"""
Do not return anything, modify rooms inplace instead.
"""
m = len(rooms)
n = len(rooms[0])
q = deque()
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
q.append((i, j))
'''
Each gate only looks at the areas within 1 space before
we check the next gate. So each area within one space of
the gates are checked for rooms and these rooms are marked,
then added to the queue. Once all gates are checked, each
new space is checked, and so forth. So, once a room gets
hit, it has to be from the closest gate.
'''
while q:
x, y = q.popleft()
for d in [(1, 0), (1, 0), (0, 1), (0, 1)]:
r = x + d[0]
c = y + d[1]
if (
r < 0 or r >= m
or c < 0 or c >= n
or rooms[r][c] != self.INF
):
continue
q.append((r, c))
rooms[r][c] = rooms[x][y] + 1
