统计子岛屿
难度:
标签:
题目描述
给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。
示例 1：
输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]] 输出：3 解释：如上图所示，左边为 grid1 ，右边为 grid2 。 grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
示例 2：
输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]] 输出：2 解释：如上图所示，左边为 grid1 ，右边为 grid2 。 grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。
提示：
m == grid1.length == grid2.lengthn == grid1[i].length == grid2[i].length1 <= m, n <= 500grid1[i][j]和grid2[i][j]都要么是0要么是1。
代码结果
运行时间: 229 ms, 内存: 25.2 MB
/*
* 思路：
* 1. 遍历grid2找到所有的岛屿。
* 2. 对每一个岛屿，检查它是否在grid1中完全存在。
* 3. 如果是，则计数加1。
* 这个版本使用Stream API来简化代码。
*/
import java.util.stream.IntStream;
public class Solution {
private int m, n;
public int countSubIslands(int[][] grid1, int[][] grid2) {
m = grid1.length;
n = grid1[0].length;
return (int) IntStream.range(0, m)
.boxed()
.flatMap(i -> IntStream.range(0, n).mapToObj(j -> new int[]{i, j}))
.filter(coords -> grid2[coords[0]][coords[1]] == 1 && grid1[coords[0]][coords[1]] == 1 && dfs(grid1, grid2, coords[0], coords[1]))
.count();
}
private boolean dfs(int[][] grid1, int[][] grid2, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid2[i][j] == 0) {
return true;
}
if (grid1[i][j] == 0) {
return false;
}
grid2[i][j] = 0;
boolean isSubIsland = true;
isSubIsland &= dfs(grid1, grid2, i + 1, j);
isSubIsland &= dfs(grid1, grid2, i - 1, j);
isSubIsland &= dfs(grid1, grid2, i, j + 1);
isSubIsland &= dfs(grid1, grid2, i, j - 1);
return isSubIsland;
}
}解释
方法:
此题解的思路是使用广度优先搜索（BFS）来遍历grid2中的每一个岛屿，并同时检查这些岛屿是否完全包含在grid1的岛屿中。从grid2的每个元素开始，如果是陆地（即值为1），则以此为起点，使用BFS遍历整个岛屿。在遍历过程中，如果发现当前岛屿的任一部分在grid1中对应的位置是水域（即值为0），则标记这个岛屿不是子岛屿。最后，如果整个岛屿在grid1中都有对应的陆地，则计数器增加。
时间复杂度:
O(m * n)
空间复杂度:
O(m * n)
代码细节讲解
🦆
在此题解中，你如何处理越界问题，尤其是在检查四周的陆地时？
▷🦆
题解中提到使用BFS进行遍历，为什么选择BFS而不是DFS？这对于解决问题有何影响？
▷🦆
在进行BFS搜索时，题解中将grid2中的元素标记为2来表示已访问，这种标记法是否可能影响原始数据结构，从而影响算法的进一步操作？
▷🦆
题解中提到如果grid2的某个部分在grid1中对应为水域，则整个岛屿不被认为是子岛屿。请问这种方法是否会漏判或误判某些情况？
▷