542.01矩阵

链接：542.01矩阵
难度：Medium
标签：广度优先搜索、数组、动态规划、矩阵
简介：给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

题解 1 - javascript

• 编辑时间：2020-04-15
• 执行用时：236ms
• 内存消耗：53.1MB
• 编程语言：javascript
• 解法介绍：广度优先搜索，一层一层判断。

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var updateMatrix = function (matrix) {
  const res = [];
  const queue = [];
  for (let i = 0; i < matrix.length; i++) {
    res.push(new Array(matrix[i].length));
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === 0) {
        queue.push([i, j]);
        res[i][j] = 0;
      }
    }
  }
  while (queue.length !== 0) {
    const [i, j] = queue.shift();
    if (i !== 0 && res[i - 1][j] === undefined) {
      res[i - 1][j] = 1 + res[i][j];
      queue.push([i - 1, j]);
    }
    if (j !== 0 && res[i][j - 1] === undefined) {
      res[i][j - 1] = 1 + res[i][j];
      queue.push([i, j - 1]);
    }
    if (i !== res.length - 1 && res[i + 1][j] === undefined) {
      res[i + 1][j] = 1 + res[i][j];
      queue.push([i + 1, j]);
    }
    if (j !== res[i].length - 1 && res[i][j + 1] === undefined) {
      res[i][j + 1] = 1 + res[i][j];
      queue.push([i, j + 1]);
    }
  }
  return res;
};

题解 2 - typescript

• 编辑时间：2021-07-25
• 执行用时：324ms
• 内存消耗：52.8MB
• 编程语言：typescript
• 解法介绍：bfs。

function updateMatrix(mat: number[][]): number[][] {
  const n = mat.length;
  const m = mat[0].length;
  const queue: [number, number, number][] = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (mat[i][j] === 0) queue.push([i, j, 0]);
    }
  }
  const format = (row: number, col: number) => `${row}::${col}`;
  const set = new Set<string>(queue.map(([row, col]) => format(row, col)));
  const add = (row: number, col: number, level: number) => {
    const str = format(row, col);
    if (set.has(str)) return;
    set.add(str);
    queue.push([row, col, level]);
  };
  while (queue.length) {
    const [row, col, level] = queue.shift()!;
    mat[row][col] = level;
    if (row > 0) add(row - 1, col, level + 1);
    if (row < n - 1) add(row + 1, col, level + 1);
    if (col > 0) add(row, col - 1, level + 1);
    if (col < m - 1) add(row, col + 1, level + 1);
  }
  return mat;
}