LeetCode 1254. 统计封闭岛屿的数目 题目描述： 想象一个二维网格，由土地（用0表示）和水（用1表示）组成。岛屿是由相邻（上下左右四个方向）的土地连接形成的区域。一个"封闭"岛屿是指这个岛屿完全被水包围，也就是说，岛屿的每一块土地都不在网格的边界上。 你的任务是，给定一个这样的二维网格，计算出其中"封闭岛屿"的数量。 例如： 网格： [ [ 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 ] ] 在这个网格中，有两个岛屿。但是，左边中间的那个岛屿有一部分土地接触到了网格的左边界，所以它不是封闭的。而中间的那个小岛屿，完全被水包围，所以它是封闭的。因此，封闭岛屿的数量是1。 解题过程： 这个问题的核心是找出所有"不接触边界"的岛屿。我们可以使用深度优先搜索（DFS）或者广度优先搜索（BFS）来标记和遍历岛屿，但需要一点小技巧。 第一步：理解关键点 一个岛屿要成为"封闭岛屿"，它的任何一块土地都不能位于网格的边界上（即第一行、最后一行、第一列、最后一列）。如果一块土地在边界上，那么由它组成的整个岛屿就不是封闭的。 第二步：设计思路 我们可以遍历网格中的每一个土地（0）。对于遇到的每一块土地，我们进行DFS或BFS，将与之相连的所有土地标记为已访问（例如，将其变成水，即1）。但是，在标记的过程中，我们需要判断这个岛屿是否接触到了边界。 如果我们在标记过程中发现任何一块土地位于边界上，那么整个岛屿就不是封闭的。 如果整个岛屿的所有土地都在网格内部，那么它就是一个封闭岛屿。 因此，我们的算法可以分成两步： "淹没"边界上的所有岛屿 ：首先，我们遍历网格的四条边界。如果边界上的某个格子是土地（0），我们就对它进行DFS/BFS，把这块土地以及所有与之相连的土地都"淹没"（标记成水，1）。这一步之后，剩下的所有土地（0）都必然是某个"封闭岛屿"的组成部分，因为它们已经不可能接触到边界了。 统计剩下的岛屿 ：现在，我们再次遍历整个网格（这次可以跳过边界，但遍历全部也没问题）。每当遇到一块土地（0），就意味着我们发现了一个新的封闭岛屿。我们对其进行DFS/BFS，标记所有相连的土地为已访问（淹没），同时将封闭岛屿的计数加一。 第三步：详细步骤（以DFS为例） 初始化 ：获取网格的行数 m 和列数 n 。 淹没边界岛屿 ： 遍历第一行（ row = 0 ）和最后一行（ row = m-1 ）的所有列。 遍历第一列（ col = 0 ）和最后一列（ col = n-1 ）的所有行。 对于上述遍历到的每一个格子 (i, j) ，如果它的值是 0 （土地），就从这个格子开始进行DFS，将整个相连的岛屿"淹没"（将格子值从 0 改为 1 ）。 统计封闭岛屿 ： 初始化计数器 count = 0 。 使用两层循环遍历网格中的每一个格子 (i, j) （ i 从 1 到 m-2 ， j 从 1 到 n-2 可以稍微优化，但遍历全部 m x n 也可以）。 如果当前格子 grid[i][j] == 0 （土地）： 将计数器 count 加 1。 从这个格子开始进行DFS，将整个相连的岛屿"淹没"（将格子值从 0 改为 1 ），以防止重复计数。 返回结果 ：返回计数器 count 的值。 第四步：DFS辅助函数的设计 DFS函数 dfs(grid, i, j) 的作用是淹没以 (i, j) 为起点的整个岛屿。 终止条件 ： 如果坐标 (i, j) 超出了网格范围（ i < 0 或 j < 0 或 i >= m 或 j >= n ），则返回。 如果当前格子已经是水（ grid[i][j] == 1 ），则返回。 处理当前节点 ：将当前土地淹没，即设置 grid[i][j] = 1 。 递归探索 ：向四个方向（上、下、左、右）递归地调用DFS。 dfs(grid, i-1, j) // 上 dfs(grid, i+1, j) // 下 dfs(grid, i, j-1) // 左 dfs(grid, i, j+1) // 右 第五步：总结 这个算法的巧妙之处在于通过一个预处理步骤（淹没边界岛屿），将问题简化为了普通的"统计岛屿数量"问题（LeetCode 200. 岛屿数量）。它确保了在第二步统计时，遇到的每一个岛屿都必然是封闭的。时间复杂度是 O(m * n)，因为每个格子最多被访问两次（一次在淹没边界时，一次在统计封闭岛屿时）。空间复杂度主要是DFS的递归栈开销，在最坏情况下是 O(m * n)。