Medium

题目描述

给你两个 m x n 的二进制矩阵 grid1 和 grid2，它们只包含 0（表示水域）和 1（表示陆地）。一个 岛屿 是由四面相连的 1 组成的一个连通分量。任何在网格外部的格子都被视为水域格子。

如果 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

解题思路

这道题的核心思想是使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历 grid2 中的每个岛屿，并检查该岛屿是否为子岛屿。

解题思路：

  1. 子岛屿的定义：grid2 中的一个岛屿是子岛屿，当且仅当该岛屿的所有格子在 grid1 中对应位置都是陆地（值为1）。

  2. 算法步骤：

    • 遍历 grid2 的每个格子
    • 当遇到未访问的陆地格子时，使用 DFS/BFS 遍历整个岛屿
    • 在遍历过程中，检查当前岛屿的每个格子在 grid1 中是否也是陆地
    • 如果岛屿中所有格子在 grid1 中都是陆地，则计数加1

  3. 优化方法：可以先将 grid2 中不符合条件的格子（即 grid2[i][j] = 1 但 grid1[i][j] = 0）直接标记为水域，这样后续遍历时只需要统计剩余的岛屿数量。

推荐解法：使用 DFS 遍历，在遍历过程中同时检查子岛屿条件，代码简洁且效率较高。

代码实现

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) {
                    if (dfs(grid1, grid2, i, j)) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
    
private:
    bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int i, int j) {
        if (i < 0 || i >= grid1.size() || j < 0 || j >= grid1[0].size() || grid2[i][j] == 0) {
            return true;
        }
        
        grid2[i][j] = 0; // 标记为已访问
        
        bool isSubIsland = grid1[i][j] == 1; // 检查当前格子是否满足子岛屿条件
        
        // 继续搜索四个方向
        isSubIsland &= dfs(grid1, grid2, i + 1, j);
        isSubIsland &= dfs(grid1, grid2, i - 1, j);
        isSubIsland &= dfs(grid1, grid2, i, j + 1);
        isSubIsland &= dfs(grid1, grid2, i, j - 1);
        
        return isSubIsland;
    }
};

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid1), len(grid1[0])
        count = 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_island = grid1[i][j] == 1  # 检查当前格子是否满足子岛屿条件
            
            # 继续搜索四个方向
            is_sub_island &= dfs(i + 1, j)
            is_sub_island &= dfs(i - 1, j)
            is_sub_island &= dfs(i, j + 1)
            is_sub_island &= dfs(i, j - 1)
            
            return is_sub_island
        
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    if dfs(i, j):
                        count += 1
        
        return count

public class Solution {
    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) {
                    if (DFS(grid1, grid2, i, j)) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
    
    private bool DFS(int[][] grid1, int[][] grid2, int i, int j) {
        if (i < 0 || i >= grid1.Length || j < 0 || j >= grid1[0].Length || grid2[i][j] == 0) {
            return true;
        }
        
        grid2[i][j] = 0; // 标记为已访问
        
        bool isSubIsland = grid1[i][j] == 1; // 检查当前格子是否满足子岛屿条件
        
        // 继续搜索四个方向
        isSubIsland &= DFS(grid1, grid2, i + 1, j);
        isSubIsland &= DFS(grid1, grid2, i - 1, j);
        isSubIsland &= DFS(grid1, grid2, i, j + 1);
        isSubIsland &= DFS(grid1, grid2, i, j - 1);
        
        return isSubIsland;
    }
}

var countSubIslands = function(grid1, grid2) {
    const m = grid1.length, n = grid1[0].length;
    let count = 0;
    
    function dfs(i, j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid2[i][j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m × n)，其中 m 和 n 分别是网格的行数和列数。每个格子最多被访问一次
空间复杂度O(m × n)，主要是递归调用栈的空间消耗，最坏情况下递归深度为 m × n

相关题目