［抄题］：
您将获得一个使用这三个可能值初始化的 m×n 2D 网格。-1 - 墙壁或障碍物。 0 - 门。 INF - Infinity是一个空房间。我们使用值 2 ^ 31 - 1 = 2147483647 来表示INF，您可以假设到门的距离小于 2147483647。
在代表每个空房间的网格中填入到距离最近门的距离。如果不可能到达门口，则应填入 INF。
给定 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[暴力解法]：
时间分析：
空间分析：
［思维问题］：
- 不知道“距离”应该对应什么数学表达式：没有抓住题目的特点，求“最短的”距离，就可以联想到最短路问题
- 在最短路问题中，以前没见过：把看似复杂的多原点-单终点 反向转化为 单原点- 多终点 增加超级源之后，多原点-多终点也能最终转换成单原点-多终点
［一句话思路］：
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 新被淹没了的x y坐标记得放到队列中
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
- 新被淹没了的x y坐标记得放到队列中
［复杂度］：Time complexity: O(m*n) 每个点都被淹没了Space complexity: O(m+n)
［英文数据结构或算法，为什么不用别的数据结构或算法］：
棋盘图：用图上的BFS
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
public class Solution {
/*
* @param rooms: m x n 2D grid
* @return: nothing
*/
//declare
int n, m;
static final int INF = 2147483647;
public void wallsAndGates(int[][] rooms) {
n = rooms.length;
if (n == 0) {
return ;
}
m = rooms[0].length;
Queue<Integer> qx = new LinkedList<>();
Queue<Integer> qy = new LinkedList<>();
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
//get all 0 into queue
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (rooms[i][j] == 0) {
qx.offer(i);
qy.offer(j);
}
}
}
while (!qx.isEmpty()) {
int cx = qx.poll();
int cy = qy.poll();
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < m &&
rooms[nx][ny] == INF) {
qx.offer(nx);
qy.offer(ny);
rooms[nx][ny] = rooms[cx][cy] + 1;//watered so shoud be put
}
}
}
}
}