01 Matrix

Description

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

 

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]
Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]
Output:
[[0,0,0],
[0,1,0],
[1,2,1]]

 

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

Solution(javascript)

/** BUG
 * @param {number[][]} matrix
 * @return {number[][]}
 */
// const updateMatrix = function (matrix) {
//   const result = new Array(matrix.length)
//     .fill(0)
//     .map(() => [])
//   const visit = (i, j) => {
//     if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[i].length) {
//       return Infinity
//     }
//     if (result[i][j] !== undefined) {
//       return result[i][j]
//     }
//     if (matrix[i][j] === 0) {
//       result[i][j] = 0
//     } else {
//       result[i][j] = Infinity // 注意这里哦
//       const temp = Math.min(
//         visit(i, j + 1),
//         visit(i, j - 1),
//         visit(i + 1, j),
//         visit(i - 1, j),
//       )
//       result[i][j] = 1 + temp
//     }
//     return result[i][j]
//   }
//   for (let i = 0; i < matrix.length; i++) {
//     for (let j = 0; j < matrix[i].length; j++) {
//       visit(i, j)
//     }
//   }
//   return result
// }

// 两轮循环，有点类似 DP 的思路
const updateMatrix = function (matrix) {
  const result = new Array(matrix.length)
    .fill(0)
    .map(() => [])
  const getValue = (i, j) => {
    if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[i].length) {
      return Infinity
    }
    return result[i][j]
  }
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === 0) {
        result[i][j] = 0
      } else {
        result[i][j] = 1 + Math.min(
          getValue(i, j - 1),
          getValue(i - 1, j),
        )
      }
    }
  }
  for (let i = matrix.length - 1; i >= 0; i--) {
    for (let j = matrix[i].length - 1; j >= 0; j--) {
      if (matrix[i][j] !== 0) {
        result[i][j] = Math.min(
          1 + Math.min(
            getValue(i, j + 1),
            getValue(i + 1, j),
          ),
          result[i][j],
        )
      }
    }
  }

  return result
}