给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
输出:
示例 2:
输入:
输出:
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
方法一：多源广度优先搜索
对于矩阵中的每一个元素，如果它的值为0，那么离它最近的0就是它自己。如果它的值为1，那么我们就需要找出离它最近的0，并且返回这个距离值。那么我们如何对于矩阵中的每一个1，都快速地找到离它最近的0呢？
我们不妨从一个简化版本的问题开始考虑起。假设这个矩阵中恰好只有一个0，我们应该怎么做？由于矩阵中只有一个0，那么对于每一个1，离它最近的0就是那个唯一的0。如何求出这个距离呢？我们可以想到两种做法：
如果0在矩阵中的位置是(i0, j0)，1在矩阵中的位置是 (i1, j1)，那么我们可以直接算出0和1之间的距离。因为我们从1到0需要在水平方向走 |i0 - i1| 步，竖直方向走 |j0 - j1| 步，那么它们之间的距离就为 |i0 - i1| + |j0 - j1|；
我们可以从0的位置开始进行广度优先搜索。广度优先搜索可以找到从起点到其余所有点的最短距离，因此如果我们从0开始搜索，每次搜索到一个1，就可以得到0到这个1的最短距离（从所有的0开始一圈一圈 向外扩散，因为每个1都是被离他最近的0扩散到的），也就离这个1最近的0的距离了（因为矩阵中只有一个0）
举个例子，如果我们的矩阵为：
1
2
3
4
| _ _ _ _
_ 0 _ _
_ _ _ _
_ _ _ _
|
其中只有一个0，剩余的1我们用短横线表示。如果我们从0开始进行广度优先搜索，那么结果依次为：
1
2
3
4
| _ _ _ _ _ 1 _ _ 2 1 2 _ 2 1 2 3 2 1 2 3
_ 0 _ _ ==> 1 0 1 _ ==> 1 0 1 2 ==> 1 0 1 2 ==> 1 0 1 2
_ _ _ _ _ 1 _ _ 2 1 2 _ 2 1 2 3 2 1 2 3
_ _ _ _ _ _ _ _ _ 2 _ _ 3 2 3 _ 3 2 3 4
|
也就是说，在广度优先搜索的每一步中，如果我们从矩阵中的位置x搜索到了位置y，并且y还没有被搜索过，那么位置y离0的距离就等于位置x离0的距离加上1。
对于上面的两种做法，第一种看上去简洁有效，只需要对每一个位置计算一下就行；第二种需要实现广度优先搜索，会复杂一些。但是，别忘了我们的题目中会有不止一个0，这样以来，如果我们要使用第一种做法，就必须对于每个1计算一次它到所有的0的距离，再从中取一个最小值，时间复杂度会非常高，无法通过本地。而对于第二种做法，我们可以很有效地处理有多个0的情况。
处理的方法很简单：我们在进行广度优先搜索的时候会使用到队列，在只有一个0的时候，我们在搜索前会把这个0的位置加入队列，才能开始进行搜索；如果有多个0，我们只需要把这些0的位置都加入队列就行了。下面的做法是多源BFS。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| var updateMatrix = function (matrix) {
if (!matrix || matrix.length === 0) return matrix;
const m = matrix.length;
const n = matrix[0].length;
const res = [];
const visited = [];
for (let i = 0; i < m; i++) {
res.push(new Array(n));
visited.push(new Array(n).fill(false));
}
const d = [[0, -1], [0, 1], [1, 0], [-1, 0]];
const q = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
res[i][j] = 0;
visited[i][j] = true;
q.push([i, j]);
}
}
}
while (q.length) {
const [x, y] = q.shift();
for (const [offsetX, offsetY] of d) {
const newX = x + offsetX;
const newY = y + offsetY;
if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
res[newX][newY] = res[x][y] + 1;
visited[newX][newY] = true;
q.push([newX, newY]);
}
}
}
return res;
};
|
方法二：记录层数的广度优先搜索
我们知道不需要知道层数的BFS的模板如下：
1
2
3
4
5
| while queue 不空：
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未访问过：
queue.push(该节点)
|
如果要确定当前遍历到了哪一层，BFS模板如下。这里增加了level表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。
1
2
3
4
5
6
7
8
9
10
| level = 0
while queue 不空：
size = queue.size()
while (size --) {
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未被访问过：
queue.push(该节点)
}
level ++;
|
上面两个是通用模板，在任何题目中都可以用，是要记住的！
上面说了这个题是多个起始点的BFS，不要害怕，就是需要先遍历一遍矩阵，把所有0先放进队列中，然后再利用模板二。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| var updateMatrix = function (matrix) {
if (!matrix || matrix.length === 0) return matrix;
const m = matrix.length;
const n = matrix[0].length;
const res = [];
const visited = [];
for (let i = 0; i < m; i++) {
res.push(new Array(n));
visited.push(new Array(n).fill(false));
}
const q = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
res[i][j] = 0;
visited[i][j] = true;
q.push([i, j]);
}
}
}
const d = [[0, -1], [0, 1], [1, 0], [-1, 0]];
let level = 0;
while (q.length) {
let size = q.length;
while (size--) {
const [x, y] = q.shift();
if (matrix[x][y] === 1) {
res[x][y] = level;
}
for (const [offsetX, offsetY] of d) {
const newX = x + offsetX;
const newY = y + offsetY;
if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
visited[newX][newY] = true;
q.push([newX, newY]);
}
}
}
level++;
}
return res;
};
|
