统计封闭岛屿的数目Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
示例 1：
输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
示例 2：
输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1
示例 3：
输入：grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
输出：2
提示：
- 1 <= grid.length, grid[0].length <= 100
- 0 <= grid[i][j] <=1
# 思路
DFS
# 解法
class Solution {
int m;
int n;
int[][] grid;
int count = 0;
public int closedIsland(int[][] grid) {
this.m = grid.length;
this.n = grid[0].length;
this.grid = grid;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j] == 0) {
if(DFS(i,j)) count++;
}
}
}
return count;
}
private boolean DFS(int i,int j){
if(i<0 || j<0 || i>=m || j>=n) return false;
if(grid[i][j]==0){
grid[i][j] = 1;
boolean up = DFS(i-1,j);
boolean down = DFS(i+1,j);
boolean left = DFS(i,j-1);
boolean right = DFS(i,j+1);
return (up && down && left && right);
}
return true;
}
}
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
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
# 总结
- 分析出几种情况，然后分别对各个情况实现
