1162. As Far from Land as Possible ⭐
Medium
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. If no land or water exists in the grid, return -1
.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|
.Example 1:
Input: grid = [[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: grid = [[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.
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j]
is0
or1
func maxDistance(grid [][]int) int {
res := 0
for i:=0; i<len(grid); i++ {
for j:=0; j<len(grid[0]); j++ {
if grid[i][j] == 1 { continue }
grid[i][j] = 201
if i > 0 {
grid[i][j] = min(grid[i][j], grid[i - 1][j] + 1)
}
if j > 0 {
grid[i][j] = min(grid[i][j], grid[i][j - 1] + 1)
}
}
}
for i:=len(grid)-1; i>=0;i-- {
for j:=len(grid)-1; j>=0; j-- {
if grid[i][j] == 1 { continue }
if i < len(grid) - 1 {
grid[i][j] = min(grid[i][j], grid[i + 1][j] + 1)
}
if j < len(grid) - 1 {
grid[i][j] = min(grid[i][j], grid[i][j + 1] + 1)
}
res = max(res, grid[i][j])
}
}
if res == 201 { return -1 }
return res - 1
}
func min(a, b int) int {
if a < b { return a }
return b
}
func max(a, b int) int {
if a > b { return a }
return b
}