1162. 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. 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
Solutions
Solution 1: BFS
We can add all land cells to the queue $q$. If the queue is empty, or the number of elements in the queue equals the number of cells in the grid, it means that the grid contains only land or ocean, so return $-1$.
Otherwise, we start BFS from the land cells. Define the initial step count $ans=-1$.
In each round of search, we spread all cells in the queue in four directions. If a cell is an ocean cell, we mark it as a land cell and add it to the queue. After a round of spreading, we increase the step count by $1$. Repeat this process until the queue is empty.
Finally, we return the step count $ans$.
The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the side length of the grid.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|