leetcode：1905. 统计子岛屿

题目

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个岛屿是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿完全包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的数目。

示例 1：
[中等] 1905. 统计子岛屿 - 图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：
[中等] 1905. 统计子岛屿 - 图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 个子岛屿。

解答 & 代码

[中等] 1254. 统计封闭岛屿的数目
本题和上面这道求封闭岛屿的数目的思路基本一致。
只要先遍历 **grid2**，将不是子岛屿的岛屿都淹没（去除），剩下的岛屿就都是子岛屿，统计子岛屿个数即可。
如何判断是否是子岛屿？

如果当前格子 grid2[row][col] == 1 && grid1[row][col] == 0，也就是说 grid2 中当前格子是陆地，而 grid1 中当前格子是海水，那么当前格子所在的岛屿肯定不是子岛屿，需要先去除

class Solution {
private:
  // 深度优先搜索，淹没 (row, col) 所在的岛屿的每个单元格
  // 即，从位置 (row, col) 开始，将与之相邻的都置 0（淹没）
  void dfs(vector<vector<int>>& grid, int row, int col)
  {
      int rows = grid.size();
      int cols = grid[0].size();
      // 递归结束条件：越界 or 已经是海水
      if(row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == 0)
          return;
      // 将 (row, col) 位置置 0，即将当前格子淹没
      grid[row][col] = 0;
      // 递归搜索上、下、左、右，将当前岛屿的每个位置都变为 0（淹没）
      dfs(grid, row - 1, col);
      dfs(grid, row + 1, col);
      dfs(grid, row, col - 1);
      dfs(grid, row, col + 1);
  }
public:
  int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
      if(grid1.size() == 0 || grid1[0].size() == 0)
          return 0;
      int rows = grid1.size();
      int cols = grid1[0].size();

      // 1. 去掉（淹没）grid2 中不是子岛屿的岛屿
      for(int row = 0; row < rows; ++row)
      {
          for(int col = 0; col < cols; ++col)
          {
              if(grid2[row][col] == 1 && grid1[row][col] == 0)
                  dfs(grid2, row, col);
          }
      }

      // 2. 剩下的都是子岛屿，统计子岛屿个数
      int subIslandsCnt = 0;
      for(int row = 0; row < rows; ++ row)
      {
          for(int col = 0; col < cols; ++col)
          {
              if(grid2[row][col] == 1)
              {
                  ++subIslandsCnt;
                  dfs(grid2, row, col);
              }
          }
      }
      return subIslandsCnt;
  }
};

复杂度分析：设矩阵 M 行 N 列

时间复杂度 O(MN)
空间复杂度 O(MN)：在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN，即空间复杂度达到 O(MN)

执行结果：

执行结果：通过

执行用时：280 ms, 在所有 C++ 提交中击败了 38.11% 的用户
内存消耗：85.1 MB, 在所有 C++ 提交中击败了 80.95% 的用户