地图分析


题目描述

你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋,请返回 -1。

示例1

img

输入:[[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释: 
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。

示例2

img

输入:[[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释: 
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大,最大距离为 4。

提示

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[i][j] 不是 0 就是 1

分析

这也是一道队列的题目,恰好和我曾经数据结构实验的迷宫类似
首先,将原本grid[i][j] = 1的(陆地)全部入队。
其次我们从一个陆地出发,寻找从上下左右寻找grid[i][j] = 0的地方,第一次循环(循环的结束标志为上一次加入队列的元素未处理个数),将一部分海洋变成陆地,即grid[i][j] = 1。
之后为cnt++,即走一步距离。
重复上面的动作,知道queue没有元素。此时返回cnt即为所求。

参考代码

class Solution {
public:
    const int directions[5] = {0, 1, 0, -1, 0};
    int maxDistance(vector<vector<int>>& grid) {
        int ret = 0;
        int N = grid.size();
        queue<pair<int, int>> q;
        // 将陆地(值为 1)的点入队
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    q.push({i, j});
                }
            }
        }

        // 全是海洋或全是陆地
        if (q.size() == 0 || q.size() == N * N)
            return -1;

        while (!q.empty()) {
            int s = q.size();
            int r = 0;
            while (s != 0) {
                pair<int, int> front = q.front();
                q.pop();
                // 4 个方向遍历
                for (int i = 0; i < 4; i++) {
                    int nx = front.first + directions[i];
                    int ny = front.second + directions[i + 1];
                    if (nx >= N || ny >= N || nx < 0 || ny < 0 || grid[nx][ny] == 1)
                        continue;
                    r++;
                    // 这里没有新开二位数组做记录,而是直接在原数组上做标记
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
                s--;
            }
            if (r > 0)
                ret++;
        }
        return ret;
    }
};

文章作者: 瑾年
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 瑾年 !
 上一篇
每日温度 每日温度
题目描述根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。
下一篇 
最简分数 最简分数
题目描述一个分数一般写成两个整数相除的形式:N/M,其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。现给定两个不相等的正分数 N1/M1和N2/M2,要求你按从小到大的顺序列出它们之间分母为 K 的最简分数
2021-07-17
  目录