As Far from Land as Possible

Description

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

 

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

 

Note:

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] is 0 or 1

Solution(javascript)

/* eslint-disable no-loop-func */
/*
 * @lc app=leetcode id=1162 lang=javascript
 *
 * [1162] As Far from Land as Possible
 */

// @lc code=start
/** 对比 542, DP 的解法：N*N
 * @param {number[][]} grid
 * @return {number}
 */
// const maxDistance = function (grid) {
//   const dp = grid.map(row => row.map(() => 0))
//   const getValue = (i, j) => {
//     if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length) {
//       return Infinity
//     }
//     return dp[i][j]
//   }
//   for (let i = 0; i < grid.length; i++) {
//     for (let j = 0; j < grid[i].length; j++) {
//       if (grid[i][j] === 1) {
//         dp[i][j] = 0
//       } else {
//         dp[i][j] = 1 + Math.min(
//           getValue(i - 1, j),
//           getValue(i, j - 1),
//         )
//       }
//     }
//   }
//   let max = -1
//   for (let i = grid.length - 1; i >= 0; i--) {
//     for (let j = grid[i].length - 1; j >= 0; j--) {
//       if (grid[i][j] === 0) {
//         dp[i][j] = Math.min(
//           1 + Math.min(
//             getValue(i + 1, j),
//             getValue(i, j + 1),
//           ),
//           dp[i][j],
//         )
//       }
//       if (dp[i][j] > 0 && dp[i][i] !== Infinity) {
//         max = Math.max(dp[i][j], max)
//       }
//     }
//   }
//   return max
// }

/** BFS Shortest Path: 先找出来1，然后遍历
 * @param {number[][]} grid
 * @return {number}
 */
const maxDistance = function (grid) {
  let current = []
  grid.forEach((row, i) => {
    row.forEach((x, j) => {
      if (x === 1) {
        current.push([i, j])
      }
    })
  })
  let distance = -1
  let max = -1
  while (current.length > 0) {
    distance += 1
    const next = []
    current.forEach(([i, j]) => {
      if (i >= 0 && i < grid.length && j >= 0 && j < grid[i].length && grid[i][j] !== true) {
        grid[i][j] = true
        max = distance
        next.push([i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1])
      }
    })
    current = next
  }
  return max === 0 ? -1 : max
}