给你两个 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。
深度优先搜索，或者并查集。
DFS：
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
def dfs(grid1, grid2, i, j, m, n) -> bool:
res = grid1[i][j] == 1
grid2[i][j] = 0
for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
a, b = i + x, j + y
if a >= 0 and a < m and b >= 0 and b < n and grid2[a][b] == 1:
if not dfs(grid1, grid2, a, b, m, n):
res = False
return res
m, n = len(grid1), len(grid1[0])
count = 0
for i in range(m):
for j in range(n):
if grid2[i][j] == 1 and dfs(grid1, grid2, i, j, m, n):
count += 1
return count并查集：
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
m, n = len(grid1), len(grid1[0])
p = list(range(m * n))
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
for i in range(m):
for j in range(n):
if grid2[i][j] == 1:
idx = i * n + j
if i < m - 1 and grid2[i + 1][j] == 1:
p[find(idx)] = find((i + 1) * n + j)
if j < n - 1 and grid2[i][j + 1] == 1:
p[find(idx)] = find(i * n + j + 1)
s = [0] * (m * n)
for i in range(m):
for j in range(n):
if grid2[i][j] == 1:
s[find(i * n + j)] = 1
for i in range(m):
for j in range(n):
root = find(i * n + j)
if s[root] and grid1[i][j] == 0:
s[root] = 0
return sum(s)DFS：
class Solution {
private int[][] directions = {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
public int countSubIslands(int[][] grid1, int[][] grid2) {
int m = grid1.length, n = grid1[0].length;
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1 && dfs(grid1, grid2, i, j, m, n)) {
++count;
}
}
}
return count;
}
private boolean dfs(int[][] grid1, int[][] grid2, int i, int j, int m, int n) {
boolean res = grid1[i][j] == 1;
grid2[i][j] = 0;
for (int[] direction : directions) {
int a = i + direction[0], b = j + direction[1];
if (a >= 0 && a < m && b >= 0 && b < n && grid2[a][b] == 1) {
if (!dfs(grid1, grid2, a, b, m, n)) {
res = false;
}
}
}
return res;
}
}并查集：
class Solution {
private int[] p;
public int countSubIslands(int[][] grid1, int[][] grid2) {
int m = grid2.length, n = grid2[0].length;
p = new int[m * n];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1) {
int idx = i * n + j;
if (i < m - 1 && grid2[i + 1][j] == 1) {
p[find(idx)] = find((i + 1) * n + j);
}
if (j < n - 1 && grid2[i][j + 1] == 1) {
p[find(idx)] = find(i * n + j + 1);
}
}
}
}
boolean[] s = new boolean[m * n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1) {
s[find(i * n + j)] = true;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int root = find(i * n + j);
if (s[root] && grid1[i][j] == 0) {
s[root] = false;
}
}
}
int res = 0;
for (boolean e : s) {
if (e) {
++res;
}
}
return res;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}function countSubIslands(grid1: number[][], grid2: number[][]): number {
let m = grid1.length,
n = grid1[0].length;
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid2[i][j] == 1 && dfs(grid1, grid2, i, j)) {
++ans;
}
}
}
return ans;
}
function dfs(
grid1: number[][],
grid2: number[][],
i: number,
j: number
): boolean {
let m = grid1.length,
n = grid1[0].length;
let ans = true;
if (grid1[i][j] == 0) {
ans = false;
}
grid2[i][j] = 0;
for (let [dx, dy] of [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
]) {
let x = i + dx,
y = j + dy;
if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || grid2[x][y] == 0) {
continue;
}
if (!dfs(grid1, grid2, x, y)) {
ans = false;
}
}
return ans;
}class Solution {
public:
int countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2) {
int m = grid1.size(), n = grid1[0].size();
int count = 0;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (grid2[i][j] == 1 && dfs(grid1, grid2, i, j, m, n))
{
++count;
}
}
}
return count;
}
private:
vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool dfs(vector<vector<int>> &grid1, vector<vector<int>> &grid2, int i, int j, int m, int n) {
bool res = grid1[i][j] == 1;
grid2[i][j] = 0;
for (auto direction : directions)
{
int a = i + direction[0], b = j + direction[1];
if (a >= 0 && a < m && b >= 0 && b < n && grid2[a][b] == 1)
{
if (!dfs(grid1, grid2, a, b, m, n))
{
res = false;
}
}
}
return res;
}
};func countSubIslands(grid1 [][]int, grid2 [][]int) int {
m, n := len(grid1), len(grid1[0])
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid2[i][j] == 1 && dfs(grid1, grid2, i, j, m, n) {
count++
}
}
}
return count
}
func dfs(grid1 [][]int, grid2 [][]int, i, j, m, n int) bool {
res := grid1[i][j] == 1
grid2[i][j] = 0
directions := [4][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
for _, direction := range directions {
a, b := i+direction[0], j+direction[1]
if a >= 0 && a < m && b >= 0 && b < n && grid2[a][b] == 1 {
if !dfs(grid1, grid2, a, b, m, n) {
res = false
}
}
}
return res
}