题目

你被给定一个m×n的二维网格，网格中有一下三种可能的初始化值：

  • -1表示墙或是障碍物
  • 0表示一扇门
  • INF无限表示一个空的房间。然后，我们用231 - 1 = 2147483647 代表INF。你可以认为通往门的距离总是小于2147483647的。

你要给每个空房间位上填上该房间到最近门的距离，如果如法到达门，则填INF即可。

image.png

思路

利用广度优先搜索，搜索每个空房间上下左右四个位置，直到找到最近的门或者无法到达门。

  1. from collections import deque
  2. class Solution：
  3.     def wallsAndGates(self, rooms):
  4.         """
  5.         Do not return anything, modify rooms in-place instead.
  6.         """
  7.         if not rooms or len(rooms) = 0:
  8.             return
  9.         row = len(rooms)
  10.         col = len(rooms[0])
  12.         def bfs(rooms, i, j, val):
  13.             # val代表当前环向外扩展的距离
  14.             # 每次进入下一层递归时，表示环向外扩散一层，val + 1
  15.             # nonlocal row, col
  16.             if i < 0 or i >= row or j < 0 or j >= col:
  17.                 return
  18.             if rooms[i][j] < val:
  19.                 # 如果当前位置已经找打了最近的门，直接返回。即原来是INF,在之前的扫描中已经找到了最近的门
  20.                 return
  21.             rooms[i][j] = val
  23.             bfs(rooms, i + 1, j, val + 1)
  24.             bfs(rooms, i, j + 1, val + 1)
  25.             bfs(rooms, i - 1, j, val + 1)
  26.             bfs(rooms, i, j - 1, val + 1)
  27.         for i in range(row):
  28.             for j in range(col):
  29.                 if rooms[i][j] == 0:
  30.                     bfs(rooms, i, j, 0)