给你两个 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 。
方法一：广度优先搜索
思路与算法
我们可以使用广度优先搜索（也可以使用深度优先搜索）找出所有的岛屿，具体可以参考「200. 岛屿数量」的官方题解 。
在 grid}_2 中搜索某一个岛屿的过程中，我们需要判断岛屿包含的每一个格子是否都在 grid}_1 中出现了。如果全部出现，那么将答案增加 1。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
private:
static constexpr array<array<int, 2>, 4> dirs = { { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }};
public:
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int m = grid1.size(), n = grid1[0].size();
auto bfs = [&](int sx, int sy) {
queue<pair<int,int>> q;
q.emplace(sx, sy);
grid2[sx][sy] = 0;
bool check = grid1[sx][sy];
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d][0];
int ny = y + dirs[d][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid2[nx][ny] == 1) {
q.emplace(nx, ny);
grid2[nx][ny] = 0;
if (grid1[nx][ny] != 1) {
check = false;
}
}
}
}
return check;
};
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1) {
ans += bfs(i, j);
}
}
}
return ans;
}
};
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
m, n = len(grid1), len(grid1[0])
def bfs(sx: int, sy: int) -> int:
q = deque([(sx, sy)])
grid2[sx][sy] = 0
check = (grid1[sx][sy] == 1)
while q:
x, y = q.popleft()
for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
if 0 <= nx < m and 0 <= ny < n and grid2[nx][ny] == 1:
q.append((nx, ny))
grid2[nx][ny] = 0
if grid1[nx][ny] != 1:
check = False
return int(check)
ans = 0
for i in range(m):
for j in range(n):
if grid2[i][j] == 1:
ans += bfs(i, j)
return ans
|
复杂度分析
