# 1162. As Far from Land as Possible

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]` is `0` or `1`

``````class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int step = 0, n = grid.size();
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue<vector<int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) continue;
q.push(vector<int>{i, j});
}
}
if (q.size() == 0 || q.size() == n * n) return -1;
while (!q.empty()) {
++step;
for (int k = q.size(); k > 0; --k) {
auto t = q.front(); q.pop();
for (auto dir : dirs) {
int x = t[0] + dir[0], y = t[1] + dir[1];
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 0) continue;
grid[x][y] = step;
q.push({x, y});
}
}
}
return step - 1;
}
};
``````

``````class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int res = -1, n = grid.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
grid[i][j] = 0;
helper(grid, i, j);
}
}
}
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] > 1) res = max(res, grid[i][j] - 1);
}
}
return res;
}
void helper(vector<vector<int>>& grid, int i, int j, int dist = 1) {
int n = grid.size();
if (i < 0 || j < 0 || i >= n || j >= n || (grid[i][j] != 0 && grid[i][j] <= dist)) return;
grid[i][j] = dist;
helper(grid, i - 1, j, dist + 1);
helper(grid, i + 1, j, dist + 1);
helper(grid, i, j - 1, dist + 1);
helper(grid, i, j + 1, dist + 1);
}
};
``````

``````class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
int res = 0, n = grid.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++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 (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 1) continue;
if (i < n - 1) grid[i][j] = min(grid[i][j], grid[i + 1][j] + 1);
if (j < n - 1) grid[i][j] = min(grid[i][j], grid[i][j + 1] + 1);
res = max(res, grid[i][j]);
}
}
return res == 201 ? -1 : res - 1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1162

Shortest Distance from All Buildings

01 Matrix

https://leetcode.com/problems/as-far-from-land-as-possible/

https://leetcode.com/problems/as-far-from-land-as-possible/discuss/360963/C%2B%2B-with-picture-DFS-and-BFS

https://leetcode.com/problems/as-far-from-land-as-possible/discuss/422691/7ms-DP-solution-with-example-beats-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation