原题链接在这里：https://leetcode.com/problems/walls-and-gates/
题目：
You are given a m x n 2D grid initialized with these three possible values.
-
-1- A wall or an obstacle. -
0- A gate. -
INF- Infinity means an empty room. We use the value231 - 1 = 2147483647to representINFas you may assume that the distance to a gate is less than2147483647.
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.
For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
题解：
BFS, 先把所有gate加到que中。对于每一个从que中poll出来的gate，看四个方向是否有room, 若有，把room的值改正gate + 1, 在放回到que中.
Time Complexity: O(m*n). m = rooms.length, n = rooms[0].length. 每个点没有扫描超过两遍. Space: O(m*n).
AC Java:
class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0 || rooms[0].length == 0){
return;
}
int m = rooms.length;
int n = rooms[0].length;
LinkedList<int []> que = new LinkedList<>();
int level = 1;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(rooms[i][j] == 0){
que.add(new int[]{i, j});
}
}
}
int [][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while(!que.isEmpty()){
int size = que.size();
while(size-- > 0){
int [] cur = que.poll();
for(int [] dir : dirs){
int x = cur[0] + dir[0];
int y = cur[1] + dir[1];
if(x < 0 || x >= m || y < 0 || y >= n || rooms[x][y] != Integer.MAX_VALUE){
continue;
}
que.add(new int[]{x, y});
rooms[x][y] = level;
}
}
level++;
}
}
}
跟上Robot Room Cleaner, Rotting Oranges, Shortest Distance from All Buildings.