This is the python solution for the Leetcode problem – Walls and Gates – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
x
30
30
1
class Solution(object):
2
def wallsAndGates(self, rooms):
3
"""
4
:type rooms: List[List[int]]
5
:rtype: void Do not return anything, modify rooms in-place instead.
6
"""
7
# BFS with queue
8
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
9
m = len(rooms)
10
if m == 0:
11
return
12
n = len(rooms[0])
13
q = []
14
for row in range(m):
15
for col in range(n):
16
# gate
17
if rooms[row][col] == 0:
18
q.append((row, col))
19
20
while len(q) > 0:
21
point = q.pop(0)
22
row, col = point[0], point[1]
23
for d in direction:
24
r = row + d[0]
25
c = col + d[1]
26
# wall or out of rooms
27
if r < 0 or c < 0 or r >= m or c >= n or rooms[r][c] != 2147483647:
28
continue
29
rooms[r][c] = rooms[row][col] + 1
30
q.append((r, c))