统计封闭岛屿的数目
难度:
标签:
题目描述
二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
示例 1：
输入：grid = [[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]] 输出：2 解释： 灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
示例 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,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
输出：2
提示：
1 <= grid.length, grid[0].length <= 1000 <= grid[i][j] <=1
代码结果
运行时间: 35 ms, 内存: 16.6 MB
/* 思路：使用DFS检查封闭岛屿，同时利用Java Stream API来计数和遍历。边界的处理与常规方法类似，只是在遍历时使用Stream */
import java.util.stream.IntStream;
public class SolutionStream {
public int closedIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
IntStream.range(0, rows).forEach(i -> {
IntStream.range(0, cols).forEach(j -> {
if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && grid[i][j] == 0) {
dfs(grid, i, j);
}
});
});
return (int) IntStream.range(0, rows).flatMap(i -> IntStream.range(0, cols).filter(j -> grid[i][j] == 0)).map(j -> {
dfs(grid, j / cols, j % cols);
return 1;
}).count();
}
private void dfs(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 1) {
return;
}
grid[i][j] = 1; // 标记为已访问
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}解释
方法:
此题解采用深度优先搜索（DFS）来遍历矩阵中的每个元素，寻找封闭岛屿。封闭岛屿定义为完全被1包围的0区域。解决方案中，首先通过遍历整个矩阵，每当遇到一个0，即尝试从该点出发进行DFS。在DFS过程中，首先标记当前节点为已访问（将其值置为1），然后检查其是否位于边界，若是，则当前岛屿不是封闭岛屿。DFS会递归地访问当前节点的上下左右节点。在DFS完成后，如果此岛屿是封闭的，则对结果计数器加一。通过这种方式，可以遍历整个矩阵，找出所有封闭岛屿并计数。
时间复杂度:
O(m*n)
空间复杂度:
O(m*n)
代码细节讲解
🦆
在深度优先搜索（DFS）中，你是如何处理边界条件以确保不会访问矩阵外的元素？
▷🦆
为什么在发现一个点属于边界时立即认定这个岛屿不是封闭岛屿？会不会有其他部分依然被水完全包围的情况？
▷🦆
在DFS中，你如何确保不会重复访问同一个节点，从而避免无限递归？
▷🦆
岛屿大小的计数是否对解决问题有直接帮助，还是仅仅用于辅助分析或其他目的？
▷