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.

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.

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 }