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

这道题给了一个只有0和1的二维数组,说是0表示水,1表示陆地,现在让找出一个0的位置,使得其离最近的1的距离最大,这里的距离用曼哈顿距离表示。这里最暴力的方法就是遍历每个0的位置,对于每个遍历到的0,再遍历每个1的位置,计算它们的距离,找到最小的距离保存为该0位置的距离,然后在所有0位置的距离中找出最大的。这种方法不是很高效,目测无法通过 OJ,博主都没有尝试。其实这道题的比较好的解法是建立距离场,即每个大于1的数字表示该位置到任意一个1位置的最短距离,在之前那道 Shortest Distance from All Buildings 就用过这种方法。建立距离场用 BFS 比较方便,因为其是一层一层往外扩散的遍历,这里需要注意的是要一次把所有1的位置都加入 queue 中一起遍历,而不是对每个1都进行 BFS,否则还是过不了 OJ。这里先把位置1都加入 queue,然后这里先做个剪枝,若位置1的个数为0,或者为 n^2,表示没有陆地,或者没有水,直接返回 -1。否则进行 while 循环,步数 step 加1,然后用 for 循环确保进行层序遍历,一定要将 q.size() 放到初始化中,因为其值可能改变。然后就是标准的 BFS 写法了,取队首元素,遍历其相邻四个结点,若没有越界且值为0,则将当前位置值更新为 step,然后将这个位置加入 queue 中继续遍历。循环退出后返回 step-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;
    }
};

我们也可以强行用 DFS 来做,这里对于每一个值为1的点都调用递归函数,更新跟其相连的所有0位置的距离,最终也能算出整个距离场,从而查找出最大的距离,参见代码如下:

解法二:

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);
    }
};

其实这道题的最优解法并不是 BFS 或者 DFS,而是下面这种两次扫描的方法,在之前那道 01 Matrix 中就使用过。有点像动态规划的感觉,还是建立距离场,先从左上遍历到右下,遇到1的位置跳过,然后初始化0位置的值为 201(因为n不超过 100,所以距离不会超过 200),然后用左边和上边的值加1来更新当前位置的,注意避免越界。然后从右边再遍历到左上,还是遇到1的位置跳过,然后用右边和下边的值加1来更新当前位置的,注意避免越界,同时还要更新结果 res 的值。最终若 res 为 201,则返回 -1,否则返回 res-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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation