LeetCode: As Far from Land as Possible

Posted on August 5, 2019July 26, 2020 by braindenny

As Far from Land as Possible

Similar Problems:

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 <= grid.length = grid[0].length < 100
grid[i][j] is 0 or 1

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/as-far-from-land-as-possible
// Basic Ideas: BFS
//  BFS from all 1s to 0s.
//  Stop when no 0s positions to be examined
// Complexity: Time O(n*m), Space O(n*m)
func maxDistance(grid [][]int) int {
    queue := [][]int{}
    for i, row := range grid {
        for j, v := range row {
            if v == 1 {
                queue = append(queue, []int{i, j})
            }
        }
    }
    // all nodes are 1
    if len(queue) == len(grid)*len(grid[0]) {
        return -1
    }
    level := 0
    for len(queue) > 0 {
        nexts := [][]int{}
        for _, node := range queue {
            i, j := node[0], node[1]
            for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0},
                                           []int{0, 1}, []int{0, -1}} {
                i2, j2 := i+offset[0], j+offset[1]
                if i2<0 || i2>=len(grid) || 
                        j2<0 || j2>=len(grid[0]) || grid[i2][j2] == 1 {
                    continue
                }
                grid[i2][j2] = 1
                nexts = append(nexts, []int{i2, j2})
            }
        }
        level++
        queue = nexts
    }
    // the last level is empty
    return level-1
}

Post Views: 0