663. 墙和门
中文English您将获得一个使用这三个可能值初始化的 m×n 2D 网格。-1
- 墙壁或障碍物。0
- 门。INF
- Infinity是一个空房间。我们使用值 2 ^ 31 - 1 = 2147483647
来表示INF,您可以假设到门的距离小于 2147483647
。
在代表每个空房间的网格中填入到距离最近门的距离。如果不可能到达门口,则应填入 INF
。
样例
样例1
输入:
[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
输出:
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
解释:
2D网络为:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
答案为:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
样例2
输入:
[[0,-1],[2147483647,2147483647]]
输出:
[[0,-1],[1,2]]
输入测试数据 (每行一个参数)如何理解测试数据?
BFS + 空房间变源点 >> 加进队列
接近源点的,则上下左右周围的空房间距离 = 源点 + 1 的距离
class Solution: """ @param rooms: m x n 2D grid @return: nothing """ def wallsAndGates(self, rooms): # write your code here #所有源点加进队列,如果是房间变成源点,也加入队列,循环队列,下一个房间rooms[x][y] = rooms[i][j] + 1 #边界情况 if not rooms: return #初始化 m, n = len(rooms), len(rooms[0]) queue = [] #循环所有的点,把空房间加进来 for i in range(m): for j in range(n): if (rooms[i][j] == 0): queue.append([i, j]) def bfs(x, y, value): if (x < 0 or y < 0 or x > m - 1 or y > n - 1): return #否则的话,如果是空房间的话 + 1,要在队列里面,接近源点,才会加 1,否则不变 if (rooms[x][y] == 2147483647): queue.append([x, y]) rooms[x][y] = value + 1 #pop队列,从前开始pop,如果是空房间则上一个源点 + 1的距离 while queue: curr = queue.pop(0) x = curr[0] y = curr[1] value = rooms[x][y] #如果是INF,空房间,则上一个源点 + 1的距离 bfs(x + 1, y, value) bfs(x - 1, y, value) bfs(x, y - 1, value) bfs(x, y + 1, value) return rooms