每天一道leetcode(Day 18)

542.01 矩阵

题目描述

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

示例

• 示例 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 那么当前元素到最近的 0 的步数就为其周围四个方向相邻元素到其最近的 0 的最小值加上 1，也就是说这题的状态方程为：

// i,j>0且martix[i][j] !==0
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i + 1][j], dp[i][j + 1]) + 1;

我们可以先从右上到左下进行遍历然后再从左下到右上进行遍历即可得到最终的结果。

代码

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var updateMatrix = function (matrix) {
  const rowLen = matrix.length;
  const colLen = matrix[0].length;
  if (rowLen === 0) return matrix;
  // 右上到左下遍历
  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      if (matrix[i][j] != 0) {
        matrix[i][j] = colLen + rowLen;
        if (i > 0) {
          matrix[i][j] = Math.min(matrix[i - 1][j] + 1, matrix[i][j]);
        }
        if (j > 0) {
          matrix[i][j] = Math.min(matrix[i][j - 1] + 1, matrix[i][j]);
        }
      }
    }
  }
  for (let i = rowLen - 1; i >= 0; i--) {
    for (let j = colLen - 1; j >= 0; j--) {
      if (matrix[i][j] != 0) {
        if (i < rowLen - 1) {
          matrix[i][j] = Math.min(matrix[i + 1][j] + 1, matrix[i][j]);
        }
        if (j < colLen - 1) {
          matrix[i][j] = Math.min(matrix[i][j + 1] + 1, matrix[i][j]);
        }
      }
    }
  }
  return matrix;
};

参考

542.01 矩阵