统计子岛屿

难度: Medium

给你两个 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 。

Submission

运行时间: 229 ms

内存: 25.2 MB

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        opts = None
        tmp_opts = None
        x, y = None, None
        flag = None

        m = len(grid1)
        n = len(grid1[0])

        res = 0

        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    # print(i, j)
                    opts = [(i, j)]
                    grid2[i][j] = 2
                    flag = False
                    while opts:
                        tmp_opts = []
                        for x, y in opts:
                            if grid1[x][y] == 0:
                                flag = True
                                # break
                            
                            if x > 0 and grid2[x - 1][y] == 1:
                                grid2[x - 1][y] = 2
                                tmp_opts.append((x - 1, y))
                            
                            if y > 0 and grid2[x][y - 1] == 1:
                                grid2[x][y - 1] = 2
                                tmp_opts.append((x, y - 1))
                            
                            if x + 1 < m and grid2[x + 1][y] == 1:
                                grid2[x + 1][y] = 2
                                tmp_opts.append((x + 1, y))
                            
                            if y + 1 < n and grid2[x][y + 1] == 1:
                                grid2[x][y + 1] = 2
                                tmp_opts.append((x, y + 1))
                        
                        # if flag:
                        #     break
                        opts = tmp_opts 
                    if not flag:
                        res += 1
                    # print(flag, res)
                    # print()
        return res

Explain

此题解的思路是使用广度优先搜索（BFS）来遍历grid2中的每一个岛屿，并同时检查这些岛屿是否完全包含在grid1的岛屿中。从grid2的每个元素开始，如果是陆地（即值为1），则以此为起点，使用BFS遍历整个岛屿。在遍历过程中，如果发现当前岛屿的任一部分在grid1中对应的位置是水域（即值为0），则标记这个岛屿不是子岛屿。最后，如果整个岛屿在grid1中都有对应的陆地，则计数器增加。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m = len(grid1)
        n = len(grid1[0])

        res = 0

        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:  # 找到grid2中的一个岛屿的起点
                    opts = [(i, j)]
                    grid2[i][j] = 2  # 标记为已访问
                    flag = False
                    while opts:  # BFS遍历岛屿
                        tmp_opts = []
                        for x, y in opts:
                            if grid1[x][y] == 0:  # 检查grid1中对应位置是否为水域
                                flag = True  # 是水域，当前岛屿不是子岛屿

                            # 向四个方向扩展BFS
                            if x > 0 and grid2[x - 1][y] == 1:
                                grid2[x - 1][y] = 2
                                tmp_opts.append((x - 1, y))
                            if y > 0 and grid2[x][y - 1] == 1:
                                grid2[x][y - 1] = 2
                                tmp_opts.append((x, y - 1))
                            if x + 1 < m and grid2[x + 1][y] == 1:
                                grid2[x + 1][y] = 2
                                tmp_opts.append((x + 1, y))
                            if y + 1 < n and grid2[x][y + 1] == 1:
                                grid2[x][y + 1] = 2
                                tmp_opts.append((x, y + 1))

                        opts = tmp_opts  # 更新BFS队列
                    if not flag:
                        res += 1  # 如果整个岛屿在grid1中都有对应的陆地，则计数器增加
        return res

Explore

在题解中，每次尝试向上、下、左、右四个方向扩展BFS前，都会进行边界检查，确保索引不会越界。例如，当尝试向左访问时（即x-1），会先检查x是否大于0；向下访问时（即x+1），会检查x+1是否小于行数m；向右访问（即y+1）时，会检查y+1是否小于列数n；向上访问时（即y-1），会检查y是否大于0。这些检查确保了访问的有效性，防止了数组越界错误。

BFS与DFS在许多情况下都可以用来解决类似问题，但BFS在处理此类问题时有一个优势：它按层次遍历，可以更加系统地检查每个岛屿的边界。对于本题，使用BFS有助于一层层扩展检查，易于管理和更新当前层次的岛屿节点。而DFS虽然也可行，但其递归性质可能在某些情况下导致堆栈溢出，尤其是在处理大数据集时。BFS通过使用队列管理节点，保证了空间的有效利用和计算的稳定性。

确实，将grid2中的元素标记为2是一种原地修改数据的方式，这意味着原始的grid2被改变了。这种做法减少了额外空间的需求，但同时也意味着一旦执行过算法，原始数据将不可恢复。如果在其他算法或操作中需要使用原始的grid2数据，这种修改就可能造成问题。如果保持数据不变是必要的，则应考虑使用额外的数据结构来记录节点访问状态，如使用一个同样维度的visited数组。

按照题解的逻辑，这种方法是准确的，不会漏判或误判。因为题目的要求是grid2中的岛屿必须完全包含在grid1的相应岛屿中，即grid2的每个陆地部分在grid1中也必须是陆地。一旦在BFS过程中发现grid2的陆地在grid1中对应的是水域，即可确定这部分岛屿不是子岛屿。这种检查是全面的，确保了只有完全包含在grid1岛屿中的grid2岛屿才被计数。