1254. 统计封闭岛屿的数目
网页链接
力扣LeetCode
力扣LeetCode & 每日一题，完成每日打卡，即可获得力扣积分。获得相应数量的积分，能在【力扣商店】，换取相应奖品！助力每日有题做，丰盈积分日益多！
题目描述
二维矩阵grid由0 00（土地）和1 11（水）组成。岛是由最大的4 44个方向连通的0 00组成的群，封闭岛是一个完全由1 11包围（左、上、右、下）的岛。
请返回封闭岛屿的数目。
输入描述
二维矩阵grid，由0 00（土地）和1 11（水）组成。
输出描述
返回封闭岛屿的数目。
示例 1
输入：
grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,0,1,0],[1,0,1,1,1,0,1,0],[1,0,0,0,0,0,1,0],[1,1,1,1,1,1,1,0]]输出：
2解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被1 11区域包围）。
示例 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], [1,0,0,0,0,0,0,1], [1,0,1,1,1,1,0,1], [1,0,1,0,1,0,1,0], [1,0,1,0,1,0,0,1], [1,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1]]输出：
2数据范围
- 1 ≤ grid.length , grid [ 0 ] .length ≤ 100 1 \le \text{grid.length},\ \text{grid}[0]\text{.length} \le 1001≤grid.length,grid[0].length≤100
- 0 ≤ grid [ i ] [ j ] ≤ 1 0 \le \text{grid}[i][j] \le 10≤grid[i][j]≤1
解题思路
本题是网格连通块搜索 + 边界可达性判定问题。矩阵中0表示土地，1表示水。一个“岛”是由上下左右四个方向连通的0组成的连通块；若该连通块完全被1包围、不接触矩阵边界，则它是“封闭岛屿”。因此只需找出所有由0组成的连通块，并判断其中是否有元素位于矩阵边界。
1. 封闭岛屿的判定条件
对于任意一个由0组成的四连通块：
- 若连通块中没有任何元素位于矩阵边界，则它完全被
1包围，是封闭岛屿； - 若连通块中存在元素位于矩阵边界，则它可以通过边界“通向外部”，不是封闭岛屿。
因此，问题转化为：统计所有不接触矩阵边界的0连通块数量。
2. 从内部陆地开始 DFS
由于边界上的0一定不可能是封闭岛屿的一部分，所以可以只遍历矩阵内部：
1 ≤ i ≤ m − 2 , 1 ≤ j ≤ n − 2 1 \le i \le m-2,\qquad 1 \le j \le n-21≤i≤m−2,1≤j≤n−2
当遇到一个未访问的内部陆地g[i][j] == 0时，以它为起点进行 DFS，搜索整个连通块。
DFS 过程中维护布尔变量c，表示当前连通块是否仍然是封闭的，初始为true。
3. DFS 的边界处理
在d(g, c, x, y)中：
- 若当前坐标位于矩阵边界：
- 若
g[x][y] == 0，说明该连通块接触到了边界，因此不是封闭岛屿，令c = false； - 然后直接返回；
- 若
- 若
g[x][y] != 0，说明是水或已访问，直接返回； - 否则将当前陆地标记为已访问，例如改为
1，然后递归访问上下左右四个方向。
这样，从内部陆地出发的 DFS 会标记整个连通块，并且只要连通块中任意一个陆地接触边界，就会把c置为false。
4. 统计答案
对每个内部未访问的陆地g[i][j] == 0：
- 令
c = true； - 调用 DFS 搜索该连通块；
- 若 DFS 结束后
c仍为true，说明该连通块没有接触边界，是封闭岛屿，答案加一。
最终返回统计到的封闭岛屿数量。
5. 特殊情况
若矩阵行数或列数小于3，即：
m < 3 或 n < 3 m < 3 \quad \text{或} \quad n < 3m<3或n<3
则不存在完全被水包围的内部陆地，直接返回0。
6. 复杂度分析
- 每个格子最多被访问一次，DFS 总时间复杂度为O ( m n ) O(mn)O(mn)；
- 递归栈深度最坏为O ( m n ) O(mn)O(mn)，因此空间复杂度为O ( m n ) O(mn)O(mn)。
总结
从矩阵内部的每个未访问陆地0出发进行 DFS，标记整个四连通块，并判断该连通块是否接触矩阵边界。若没有接触边界，则它是一个封闭岛屿。统计所有这样的连通块数量即可。整体是标准的网格连通块搜索问题，时间复杂度为O ( m n ) O(mn)O(mn)。
代码内容
classSolution{voidd(vector<vector<int>>&g,bool&c,intx,inty){if(x==0||x==g.size()-1||y==0||y==g[x].size()-1){if(g[x][y]==0)c=false;return;}if(g[x][y])return;g[x][y]=1;d(g,c,x-1,y);d(g,c,x+1,y);d(g,c,x,y-1);d(g,c,x,y+1);}public:intclosedIsland(vector<vector<int>>&g){intm=g.size(),n=g[0].size(),r=0;if(m<3||n<3)return0;for(inti=1;i<m-1;i++){for(intj=1;j<n-1;j++){if(g[i][j]==0){boolc=true;d(g,c,i,j);r+=c;}}}returnr;}};