给你两个 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.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[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
|
复杂度分析