问题：

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:

0 0 0

0 1 0

0 0 0

输出：

0 0 0

0 1 0

0 0 0

示例 2:

输入:

0 0 0

0 1 0

1 1 1

输出：

0 0 0

0 1 0

1 2 1

注意:

给定矩阵的元素个数不超过 10000。

给定矩阵中至少有一个元素是 0。

矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解题思路

又是一道BFS(广度优先搜索)问题，找出每个元素到最近的 0 的距离。实际上就是0到非0元素的最短距离。

通常的BFS只有一个源点，这道题可能存在多个0，开始时找到这些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
              /**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var updateMatrix = function (matrix) {
  var defaultList = [
    [-1, 0],
    [1, 0],
    [0, 1],
    [0, -1]
  ]
  var m = matrix.length;
  var n = matrix[0].length;
  var result = new Array(m);
  var visit = new Array(m);
  var queue = new Array();
  for (var i = 0; i < m; i++) {
    result[i] = new Array(n);
    visit[i] = new Array(n);
    for (var j = 0; j < n; j++) {
      var element = matrix[i][j];
      result[i][j] = 0;
      if (element === 0) {
        queue.push([i, j]);
        visit[i][j] = true;
      }
    }
  }
  while (queue.length > 0) {
    var item = queue.shift();
    var i = item[0];
    var j = item[1];
    for (var index = 0; index < 4; index++) {
      var ii = i + defaultList[index][0];
      var jj = j + defaultList[index][1];
      if (ii > -1 && ii < m && jj > -1 && jj < n && !visit[ii][jj]) {
        result[ii][jj] = result[i][j] + 1;
        queue.push([ii, jj]);
        visit[ii][jj] = true;
      }
    }
  }
  return result
};