飞地的数量Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1:
输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。
示例 2:
输入: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
# 解法
class Solution {
// 从地图四边界上的陆地往地图里面进行深搜
// 最后再遍历一遍地图,此时还存在的陆地就是无法到达的陆地
public int numEnclaves(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res = 0;
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)) && grid[i][j] == 1){
dfs(grid, i, j);
}
}
}
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == 1) res++;
}
}
return res;
}
public void dfs(int[][] grid, int i, int j){
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
return;
grid[i][j] = 0;
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 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
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
# 总结
- 分析出几种情况,然后分别对各个情况实现