VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 1162. 地图分析

Posted on Edited on In , ,

摘要：
一道经典的多源BFS题。

题目

你现在手里有一份大小为 $N*N$ 的 网格 $grid$，上面的每个 单元格 都用 $0$ 和 $1$ 标记好了。其中 $0$ 代表海洋，$1$ 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

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

如果网格上只有陆地或者海洋，请返回 $-1$。

示例 1：

0x0

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

示例 2：

0x1

输入：[[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$

多源BFS

遍历数组，将所有岛屿入队，每次根据当前结点计算出下一个海洋结点，就将海洋结点值设为父结点的值加一。
于是，就像水中的多点扰动水面一样，最终涟漪交汇的地方就是最远海洋结点。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
 * 2021-6-23 18:47:28
 * @Author: etoa
 */
static const auto shutdown = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    return nullptr;
}();

class Solution {
public:
    static constexpr int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
    static constexpr int N = 10010;

    pair<int, int> q[N];
    int hh = 0, tt = -1;

    int R, C;
    int res = -1;

    int maxDistance(vector<vector<int>>& grid) {
        this->R = grid.size(), this->C = grid[0].size();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (grid[i][j] == 1) q[++tt] = {i, j};
            }
        }

        // determine special situation
        int qsize = tt - hh + 1;
        if (qsize == R * C || !qsize) return res;

        for (; tt >= hh; ++hh) {                         // pop head
            int r = q[hh].first, c = q[hh].second;
            for (int i = 0; i < 4; i++) {
                int ner = r + dr[i], nec = c + dc[i];
                if (ner < 0 || ner > R - 1 || nec < 0 || nec > C - 1 || grid[ner][nec]) continue;
                grid[ner][nec] = grid[r][c] + 1;
                q[++tt] = {ner, nec};
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                res = max(res, grid[i][j]);
                //cout << grid[i][j] << ' ';
            }
            //cout << endl;
        }
        return res - 1;
    }
};

原题链接： LeetCode 1162. 地图分析