【广度优先搜索】leetcode 1162. 地图分析

1162. 地图分析

题目描述

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例1：

输入： grid = [[1,0,1],[0,0,0],[1,0,1]]
输出： 2
解释： 海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例2：

输入： grid = [[1,0,0],[0,0,0],[0,0,0]]
输出： 4
解释： 海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

提示

• $n==grid.length$
• $n==grid[i].length$
• $1<=n<=100$
• $grid[i][j]不是0就是1$

方法：广度优先搜索

解题思路

相信对于 $Tree$ 的 $BFS$ 大家都已经轻车熟路了：要把 $root$ 节点先入队，然后再一层一层的无脑遍历就行了。

对于图的 $BFS$也是一样滴～ 与 $Tree$ 的 $BFS$ 区别如下：
1、$tree$ 只有1个 $root$，而图可以有多个源点，所以首先需要把多个源点都入队。
2、$tree$ 是有向的因此不需要标志是否访问过，而对于无向图来说，必须得标志是否访问过！
并且为了防止某个节点多次入队，需要在入队之前就将其设置成已访问！

这是一道典型的 $BFS$ 基础应用，为什么这么说呢？
因为我们只要先把所有的陆地都入队，然后从各个陆地同时开始一层一层的向海洋扩散，那么最后扩散到的海洋就是最远的海洋！并且这个海洋肯定是被离他最近的陆地给扩散到的！

代码

class Solution {
public:
    const int dx[4] = {1, 0, -1, 0};
    const int dy[4] = {0, 1, 0, -1};
    int maxDistance(vector<vector<int>>& grid) {
        int nr = grid.size(), nc = grid[0].size();
        queue<pair<int, int>> que;
        for(int r = 0; r < nr; r++) 
            for(int c = 0; c < nc; c++)
                if(grid[r][c] == 1)
                    que.push({r, c});
        if(que.size() == 0 || que.size() == nr * nc)    return -1;
        int distance = -1;
        while(!que.empty()) {
            distance++;
            int size = que.size();
            for(int i = 0; i < size; i++) {
                auto cur = que.front();
                que.pop();
                for(int j = 0; j < 4; j++) {
                    int mx = cur.first + dx[j], my = cur.second + dy[j];
                    if(mx < 0 || mx >= nr || my < 0 || my >= nc || grid[mx][my] != 0) 
                        continue;
                    grid[mx][my] = 2;
                    que.push({mx, my});
                }
            }
        }
        return distance;
    }
};
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