给定一个由 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。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

方法一:多源广度优先搜索

对于矩阵中的每一个元素,如果它的值为0,那么离它最近的0就是它自己。如果它的值为1,那么我们就需要找出离它最近的0,并且返回这个距离值。那么我们如何对于矩阵中的每一个1,都快速地找到离它最近的0呢?

我们不妨从一个简化版本的问题开始考虑起。假设这个矩阵中恰好只有一个0,我们应该怎么做?由于矩阵中只有一个0,那么对于每一个1,离它最近的0就是那个唯一的0。如何求出这个距离呢?我们可以想到两种做法:

  • 如果0在矩阵中的位置是(i~0~, j~0~),1在矩阵中的位置是 (i~1~, j~1~),那么我们可以直接算出0和1之间的距离。因为我们从1到0需要在水平方向走 |i~0~ - i~1~| 步,竖直方向走 |j~0~ - j~1~| 步,那么它们之间的距离就为 |i~0~ - i~1~| + |j~0~ - j~1~|;

  • 我们可以从0的位置开始进行广度优先搜索。广度优先搜索可以找到从起点到其余所有点的最短距离,因此如果我们从0开始搜索,每次搜索到一个1,就可以得到0到这个1的最短距离(从所有的0开始一圈一圈 向外扩散,因为每个1都是被离他最近的0扩散到的),也就离这个1最近的0的距离了(因为矩阵中只有一个0)

举个例子,如果我们的矩阵为:

_ _ _ _
_ 0 _ _
_ _ _ _
_ _ _ _

其中只有一个0,剩余的1我们用短横线表示。如果我们从0开始进行广度优先搜索,那么结果依次为:

_ _ _ _         _ 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

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]]; // 4个方向数组

  // bfs
  // 1.将等于0的位置直接放入结果集并入队作为广度优先的起点(多起点的BFS)
  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]);
      }
    }
  }

  // 2.多起点的广度优先
  while (q.length) {
    const [x, y] = q.shift();
    for (const [offsetX, offsetY] of d) {
      const newX = x + offsetX;
      const newY = y + offsetY;
      // 没有访问过的地方一定是1,因为第一步中值为0的位置全部被标记了
      if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
        // (newX,newY) 是 (x,y)的相邻节点
        res[newX][newY] = res[x][y] + 1;
        visited[newX][newY] = true;
        q.push([newX, newY]);
      }
    }
  }

  return res;
};

方法二:记录层数的广度优先搜索

我们知道不需要知道层数的BFS的模板如下:

while queue 不空:
    cur = queue.pop()
    for 节点 in cur的所有相邻节点:
        if 该节点有效且未访问过:
            queue.push(该节点)

如果要确定当前遍历到了哪一层,BFS模板如下。这里增加了level表示当前遍历到二叉树中的哪一层了,也可以理解为在一个图中,现在已经走了多少步了。size表示在当前遍历层有多少个元素,也就是队列中的元素数,我们把这些元素一次性遍历完,即把当前层的所有元素都向外走了一步。

level = 0
while queue 不空:
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点:
            if 该节点有效且未被访问过:
                queue.push(该节点)
    }
    level ++;

上面两个是通用模板,在任何题目中都可以用,是要记住的!

上面说了这个题是多个起始点的BFS,不要害怕,就是需要先遍历一遍矩阵,把所有0先放进队列中,然后再利用模板二。

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 = [];
    // 如果(i,j)元素为0,则 距离为0
    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;
                // 没有访问过的地方一定是1,因为第一步中值为0的位置全部被标记了
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    q.push([newX, newY]);
                }
            }
        }
        level++;
    }

    return res;
};