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.lengthn == grid[i].length1 <= n <= 100grid[i][j] is 0 or 1
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(n2), and the space complexity is O(n2). Here, n is the side length of the grid.
PythonJavaC++GoTypeScript
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
n = len(grid)
q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j])
ans = -1
if len(q) in (0, n * n):
return ans
dirs = (-1, 0, 1, 0, -1)
while q:
for _ in range(len(q)):
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
grid[x][y] = 1
q.append((x, y))
ans += 1
return ans(code-box)
class Solution {
public int maxDistance(int[][] grid) {
int n = grid.length;
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
q.offer(new int[] {i, j});
}
}
}
int ans = -1;
if (q.isEmpty() || q.size() == n * n) {
return ans;
}
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
for (int i = q.size(); i > 0; --i) {
int[] p = q.poll();
for (int k = 0; k < 4; ++k) {
int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0) {
grid[x][y] = 1;
q.offer(new int[] {x, y});
}
}
}
++ans;
}
return ans;
}
}(code-box)
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int n = grid.size();
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j]) {
q.emplace(i, j);
}
}
}
int ans = -1;
if (q.empty() || q.size() == n * n) {
return ans;
}
int dirs[5] = {-1, 0, 1, 0, -1};
while (!q.empty()) {
for (int m = q.size(); m; --m) {
auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && !grid[x][y]) {
grid[x][y] = 1;
q.emplace(x, y);
}
}
}
++ans;
}
return ans;
}
};(code-box)
func maxDistance(grid [][]int) int {
n := len(grid)
q := [][2]int{}
for i, row := range grid {
for j, v := range row {
if v == 1 {
q = append(q, [2]int{i, j})
}
}
}
ans := -1
if len(q) == 0 || len(q) == n*n {
return ans
}
dirs := [5]int{-1, 0, 1, 0, -1}
for len(q) > 0 {
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p[0]+dirs[k], p[1]+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 {
grid[x][y] = 1
q = append(q, [2]int{x, y})
}
}
}
ans++
}
return ans
}(code-box)
function maxDistance(grid: number[][]): number {
const n = grid.length;
const q: [number, number][] = [];
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
q.push([i, j]);
}
}
}
let ans = -1;
if (q.length === 0 || q.length === n * n) {
return ans;
}
const dirs: number[] = [-1, 0, 1, 0, -1];
while (q.length > 0) {
for (let m = q.length; m; --m) {
const [i, j] = q.shift()!;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] === 0) {
grid[x][y] = 1;
q.push([x, y]);
}
}
}
++ans;
}
return ans;
}(code-box)
