统计封闭岛屿的数目【力扣LeetCode 每日一题】-平芜编程栈

1254. 统计封闭岛屿的数目

网页链接

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]]

输出：

解释：

灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被1 11区域包围）。

示例 2

输入：

grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]

输出：

示例 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]]

输出：

数据范围

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;}};