0286. 墙与门

0286. 墙与门#

• 标签：广度优先搜索
• 难度：中等

题目大意 #

• -1 表示墙或者障碍物
• 0 表示一扇门
• INF 表示为一个空的房间。这里用 $2^{31} = 2147483647$ 表示 INF。通往门的距离总是小于 $2^{31}$。

代码 #

  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))