🕹︎ 1020.飞地的数量
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
思路
基本思想
按照题目的描述，就是求那些陆地不能到达给定的图的边界，而一旦岛屿中的某一个陆地的上下左右的任意一个方向能够到达边界，那么整个岛屿中就没有”飞地“，也就是所有的陆地都能到达边界
所以将岛屿求面积的算法进行简单改进，在求岛屿面积的时候，将返回条件分开，一旦某一个陆地的上下左右四个方向中有一个方向到达边界，那么这整个岛屿都能到达边界，也就是说岛屿中不存在飞地
所以一旦超过边界，就可以返回true，这样一层一层的返回，最终岛屿就会返回true，而遇到了海洋和已遍历过的陆地，就暂时返回false，并且在遍历的过程中还需要统计岛屿的面积，因为一旦岛屿中出现飞地，也就是岛屿中的所有陆地都无法到达边界，最终就会返回false，那么岛屿中飞地的数量就是岛屿的面积
需要注意的是，遍历当前陆地的上下左右四个方向时，需要分开遍历，因为合在一起遍历，一旦出现一个true，岛屿没有遍历结束就会返回，剩下没有遍历的陆地就会被认为是一个新的陆地，可能造成飞地的数量变多，这是c++语法的问题，不是解题思路的问题
执行流程
- 遍历图中所有的节点，一旦出现陆地就开始统计面积
- 统计面积时一旦遇到边界，说明这个岛屿能够到达边界，返回true
- 遇到海洋或者已遍历的陆地时暂时返回false
- 将当前的陆地标记为已统计，同时岛屿的面积+1
- 上下左右四个方向分开进行统计，防止程序提前返回
- 返回四个方向的或，这样一旦出现一个true（能够到达边界），所有的陆地都返回true，最终说明岛屿能够到达边界
- 如果统计岛屿面积的时候，岛屿无法到边界，也就是返回了false，此时统计飞地的数量，也就是岛屿的面积
- 返回飞地的数量
代码
根据以上分析，得出以下代码：
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
| class Solution {
public:
//统计的就是无法离开边界的陆地的数量
//改造岛屿面积统计的函数
//一旦某个陆地遇到了边界，那么这个岛屿中的所有陆地都可以离开边界，不是飞地
//当一个岛屿中没有任何一个陆地的上下左右能够遇到边界，说明这个岛屿的所有陆地都是飞地
//此时这个岛屿的面积就是岛屿中飞地的数量
int numEnclaves(vector<vector<int>>& grid) {
//初始飞地数量为0
int res=0;
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[0].size();++j){
if(grid[i][j]==1){
int area=0;
bool flag=dfs(grid,area,i,j);
//当前岛屿是飞地，也就是无法到达边界
if(!flag){
res+=area;
}
}
}
}
return res;
}
//bool代表该岛屿能不能够到达边界
bool dfs(vector<vector<int>>& grid,int& area,int x,int y){
//超过边界，说明这个岛屿可以到达边界，其中的陆地不是飞地
if(x<0||y<0||x>=grid.size()||y>=grid[0].size()){
return true;
}
//遇到海洋或者遇到已遍历的陆地，暂时返回false
if(grid[x][y]==0||grid[x][y]==2){
return false;
}
//标记当前陆地为已遍历，并统计岛屿的面积
grid[x][y]=2;
//如果当前岛屿是飞地，那么面积就是当前岛屿中飞地的数量
area+=1;
//一旦有一个陆地接触到了边界就说明不是飞地，直接返回true
//有一个为真就为真
//如果上下左右不分开的话，那么一旦遇到一个真就会直接返回，后面的陆地就不会统计
//此时岛屿就无法统计完全，所以需要强行将四个遍历语句分开
//从而使得岛屿的遍历完全
bool up=dfs(grid,area,x-1,y);
bool down=dfs(grid,area,x+1,y);
bool left=dfs(grid,area,x,y-1);
bool right=dfs(grid,area,x,y+1);
return up||down||left||right;
}
};
|
总结
一旦有陆地能够到达边界，这个岛屿就不存在飞地，统计当前陆地的上下左右时，记得分开统计，合在一起统计时，一旦出现一个true，程序就会提前返回，此时岛屿中剩下的节点没有被标记为已访问，程序认为这是一个新的岛屿，会造成意想不到的错误