01 矩阵

题目

题目来源：力扣（LeetCode）

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function (matrix) {
  if (!matrix.length || !matrix[0].length) return null;
  let n = matrix.length;
  let m = matrix[0].length;
  // 初始化一个与源矩阵 matrix 一样长度的数组
  let ans = new Array(n);
  // 初始化一个新的矩阵，并且矩阵的值都初始化为 -1
  for (let i = 0; i < n; i++) ans[i] = new Array(m).fill(-1);
  let queue = [];
  // 遍历矩阵 matrix，找到所有 0 的位置 [i， j]，将 0 的位置放入队列，并将 ans 矩阵中 [i, j] 的位置的值重置为 0
  for (let i = 0; i < n; i++)
    for (let j = 0; j < m; j++) {
      if (matrix[i][j] === 0) {
        ans[i][j] = 0;
        queue.push([i, j]);
      }
    }
  let dist = 0;
  while (queue.length) {
    let len = queue.length;
    dist++;
    for (let i = 0; i < len; i++) {
      let top = queue.shift();
      if (top[0] + 1 < n && ans[top[0] + 1][top[1]] === -1) {
        queue.push([top[0] + 1, top[1]]);
        ans[top[0] + 1][top[1]] = dist;
      }
      if (top[0] - 1 >= 0 && ans[top[0] - 1][top[1]] === -1) {
        queue.push([top[0] - 1, top[1]]);
        ans[top[0] - 1][top[1]] = dist;
      }
      if (top[1] + 1 < m && ans[top[0]][top[1] + 1] === -1) {
        queue.push([top[0], top[1] + 1]);
        ans[top[0]][top[1] + 1] = dist;
      }
      if (top[1] - 1 >= 0 && ans[top[0]][top[1] - 1] === -1) {
        queue.push([top[0], top[1] - 1]);
        ans[top[0]][top[1] - 1] = dist;
      }
    }
  }
  return ans;
};