LC 1020. 飞地的数量
题目描述
这是 LeetCode 上的 1020. 飞地的数量 ,难度为 中等。
给你一个大小为 $m x n$ 的二进制矩阵 $grid$ ,其中 $0$ 表示一个海洋单元格、$1$ 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 $grid$ 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1:1
2
3
4
5输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。
示例 2:1
2
3
4
5输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出:0
解释:所有 1 都在边界上或可以到达边界。
提示:
- $m == grid.length$
- $n == grid[i].length$
- $1 <= m, n <= 500$
- $grid[i][j]$ 的值为 $0$ 或 $1$
并查集 + DFS
根据题目定义,我们知道需要统计所有不和「边缘陆地」相连通的「普通陆地」数量。
我们可以用「并查集」来维护连通块,使用 DFS
对所有「边缘陆地连通块」进行标记(设定编号为 $0$ 的超级源点,对于所有的「边缘陆地连通块」,将其与超级源点联通)。
具体的,我们按照如下流程进行处理:
- 初始化并查集:起始让每个单元格独立作为一个连通块;
- 使用
DFS
标记所有「边缘陆地连通块」:从位于边缘的「边缘陆地」进行出发,将其所在连通块与超级源点 $0$ 进行联通标记(同时为了确保复杂度,我们在进行DFS
前需要先检查当前陆地与超级源点的联通关系,如果已联通,说明当前陆地棣属于之前的某个连通块,已被整体标记过,进行跳过即可); - 统计答案:遍历整个棋盘,统计所有不与超级源点 $0$ 联通的陆地数量。
一些细节:由于我们人为规定了超级源点编号为 $0$,同时棋盘下标从 $0$ 开始,因此对某个点 $(x, y)$ 的编号,我们需要增加一个偏移量,例如 $idx = x * n + y + 1$。
代码: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
53class Solution {
int N = 550;
int[] p = new int[N * N];
int m, n;
int[][] g;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
boolean query(int a, int b) {
return find(a) == find(b);
}
void union(int a, int b) {
p[find(a)] = find(b);
}
public int numEnclaves(int[][] grid) {
g = grid;
m = g.length; n = g[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
p[getIdx(i, j)] = getIdx(i, j);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
if (g[i][j] != 1 || query(getIdx(i, j), 0)) continue;
dfs(i, j);
}
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 1 && !query(getIdx(i, j), 0)) ans++;
}
}
return ans;
}
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x, int y) {
union(getIdx(x, y), 0);
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (g[nx][ny] != 1 || query(getIdx(nx, ny), 0)) continue;
dfs(nx, ny);
}
}
int getIdx(int x, int y) {
return x * n + y + 1;
}
}
- 时间复杂度:初始化并查集复杂度为 $O(m n)$;使用
DFS
对边缘陆地连通块进行标记复杂度为 $O(m n)$;统计答案复杂度为 $O(m n)$。整体复杂度为 $O(m n)$ - 空间复杂度:$O(m * n)$
多源 BFS
也可以使用「多源 BFS
」进行求解。
将所有「边缘陆地」看做与超级源点相连,起始将所有「边缘陆地」进行入队(等价于只将超级源点入队,然后取出超级源点并进行拓展)。
然后是常规的 BFS
过程,所有能够出队/入队的陆地格子,都代表与「边缘陆地」联通,都不属于「飞地」,对其进行标记。
最后遍历整个棋盘,统计所有未被标记的「陆地」格子数量即是答案。
不熟悉「多源 BFS
」的同学可以看前置 🧀 :多源 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
36class Solution {
public int numEnclaves(int[][] g) {
int m = g.length, n = g[0].length;
boolean[][] vis = new boolean[m][n];
Deque<int[]> d = new ArrayDeque<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
if (g[i][j] == 0) continue;
vis[i][j] = true;
d.addLast(new int[]{i, j});
}
}
}
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
while (!d.isEmpty()) {
int[] poll = d.pollFirst();
int x = poll[0], y = poll[1];
for (int[] di : dirs) {
int nx = x + di[0], ny = y + di[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (g[nx][ny] != 1) continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = true;
d.addLast(new int[]{nx, ny});
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 1 && !vis[i][j]) ans++;
}
}
return ans;
}
}
- 时间复杂度:$O(m * n)$
- 空间复杂度:$O(m * n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1011
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!