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≤1000 ≤ 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 3m3或n3则不存在完全被水包围的内部陆地直接返回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(vectorvectorintg,boolc,intx,inty){if(x0||xg.size()-1||y0||yg[x].size()-1){if(g[x][y]0)cfalse;return;}if(g[x][y])return;g[x][y]1;d(g,c,x-1,y);d(g,c,x1,y);d(g,c,x,y-1);d(g,c,x,y1);}public:intclosedIsland(vectorvectorintg){intmg.size(),ng[0].size(),r0;if(m3||n3)return0;for(inti1;im-1;i){for(intj1;jn-1;j){if(g[i][j]0){boolctrue;d(g,c,i,j);rc;}}}returnr;}};