1905. 统计子岛屿 - Count Sub Islands

🎯 问题描述（来源于LeetCode）

描述：
给定两个 m x n 的二进制矩阵 grid1 和 grid2，其中 1 表示陆地，0 表示水域。
如果 grid2 中的一个岛屿（由四方向相连的 1 组成）的所有格子，在 grid1 的对应位置也都是陆地（即 grid1 中也全为 1），则称该岛屿是 grid2 的一个子岛屿。
请返回 grid2 中子岛屿的数量。

说明：

岛屿定义为四方向连通的 1 组成的区域。
子岛屿的所有格子必须在 grid1 中也是陆地，但 grid1 中可能存在额外的陆地（不在该岛屿内）。

示例：

示例 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
解释: grid2 中有三个子岛屿（分别位于左上、右下等）。

示例 2：

1
2
3

输入: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0]], 
       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

💻 解题思路

思路：DFS 遍历 grid2 的岛屿并验证 grid1

算法步骤

获取网格尺寸 m, n。
定义 DFS 函数 dfs(i, j)：
- 如果坐标越界或 grid2[i][j] == 0，返回 True（边界外或水域不影响当前岛屿的验证）。
- 将 grid2[i][j] 标记为 0（表示已访问，同时淹没该格子）。
- 判断当前格子是否在 grid1 中也是陆地：is_sub = (grid1[i][j] == 1)。
- 对四个方向递归调用 dfs，并将返回值与 is_sub 进行逻辑与运算（and）：
  is_sub = dfs(i+di, j+dj) and is_sub
  注意顺序：先递归再与 is_sub 结合，确保所有方向都返回 True 且当前格子也是陆地时，is_sub 才为 True。
- 返回 is_sub（表示以 (i, j) 为起点的岛屿是否为子岛屿）。
遍历 grid2 的每个格子，如果发现 grid2[i][j] == 1，则调用 dfs(i, j)，若返回 True 则计数加一。
返回计数 ans。

代码实现

from typing import List

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid1), len(grid1[0])
        
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid2[i][j] == 0:
                return True
            grid2[i][j] = 0  # 标记已访问
            is_sub = (grid1[i][j] == 1)
            for di, dj in ((1,0), (-1,0), (0,1), (0,-1)):
                is_sub = dfs(i + di, j + dj) and is_sub
            return is_sub
        
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    if dfs(i, j):
                        ans += 1
        return ans

📊 性能分析

时间复杂度： $O(m \times n)$ ，每个格子最多被访问一次。
空间复杂度： $O(m \times n)$ ，递归栈深度最坏为岛屿大小（可能接近 $m \times n$ ）。

思考

代码中 is_sub = dfs(...) and is_sub 的顺序不能颠倒。
如果写成 is_sub = is_sub and dfs(...)，当 is_sub 为 False 时，and 会短路，dfs(...) 不会执行，导致该方向上的岛屿格子未被标记为 0，后续可能会被重复访问或残留，影响最终结果。
因此必须把 dfs(...) 放在左侧，确保整个岛屿的所有格子都被遍历并标记淹没，同时通过 and 将各个方向的验证结果累加到 is_sub 中。
本解法直接修改 grid2，省去了 visited 数组。
也可用 BFS 实现，避免递归深度过大