统计子岛屿 图解题解

grid2 里哪些岛被 grid1 的陆地整块托住

两张一样大的网格 grid1 和 grid2，只有 0 和 1，1 是陆地、0 是水，上下左右连成一片的陆地就是一座岛屿。grid2 的某座岛屿，若它盖住的每一格在 grid1 里也全是陆地，就叫子岛屿，要数的正是这种岛有几座。题面 grid2=[[1,1,1,0],[0,1,0,0],[0,0,0,1],[1,1,0,1]] 配 grid1=[[1,1,0,0],[0,1,0,0],[0,0,0,1],[1,1,1,1]]，答案是 2。

把两张图的岛一一配对去比，对不上

拿 grid2 的岛和 grid1 的岛一对一比形状，立刻卡住：子岛屿根本不要求两边是同一座岛的同一形状，只要 grid2 这块盖住的格子在 grid1 都踩着陆地就行。grid1 的一整片陆地里就能装下 grid2 的好几座小岛，按整岛配对从一开始就问错了问题。

改成按格判托底，一块岛只问一个问题

把问题缩到一格：grid2 这块岛里，有没有哪一格在 grid1 是水？一个都没有，这块就过关。走遍一整块岛用 DFS，也就是踩着相连的陆地一格接一格递归铺开；为了不把同一块岛数第二遍，走过的 grid2 格子随手改成 0 沉掉，这叫沉岛，省下另开一张标记表。沿路给这块岛记一个 ok，起点取它在 grid1 的值，每多踩一格就和那格的 grid1 值按位与一下——碰上 0，ok 就归 0，这块岛作废。

外层扫 grid2，踩了洞也得把整块走完

外层循环从左上角逐格扫 grid2，碰到还没沉的陆地就以它为起点发起 DFS，把整块岛走遍，DFS 的返回值就是这块岛的 ok，累加进答案。这里有个反直觉处：某格发现 grid1 是水、ok 已归 0，也绝不能当场收手返回。剩下的陆地还得走遍沉掉，不然这些残格会被外层当成没碰过的新岛屿，再数一遍，答案偏大。

拿题面这两张网格逐块搜一趟

外层先撞上 (0,0)，发起第一次 DFS。起点 grid1 是 1，ok 记成 1；按上右下左的顺序钻到 (0,1) 还是 1，再钻到 (0,2)——它在 grid1 是 0，ok 当场压成 0；可 DFS 不收手，回头把 (1,1) 也走遍沉掉。这块 4 格岛因为 (0,2) 的洞，ok 收成 0，不加。

外层接着走，沉掉的格子全跳过，撞上 (2,3) 连到 (3,3)，两格在 grid1 都是 1，ok 全程是 1，加到 1；再撞上 (3,0) 连到 (3,1)，两格也都托底，ok 又是 1，加到 2。三座岛查完，答案 2。

最容易漏沉、错扫的那几处

另一个易错点是外层别错扫 grid1 的陆地——起点和连通都以 grid2 为准，grid1 只当那把量托底的尺子。边界上，两张网格都只有一格陆地且都是 1 时答案是 1；grid2 陆地而 grid1 是水的格子就是个洞。时间上外层扫一遍、每个陆地格只被 DFS 沉一次，合起来 O(m·n)；空间按峰值算，原地沉岛不另开表，递归栈最坏排到格子总数量级，同样 O(m·n)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            ok = grid1[i][j]
            grid2[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid2[x][y] and not dfs(x, y):
                    ok = 0
            return ok

        m, n = len(grid1), len(grid1[0])
        dirs = (-1, 0, 1, 0, -1)
        return sum(dfs(i, j) for i in range(m) for j in range(n) if grid2[i][j])

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid1.size(), n = grid1[0].size();
        int ans = 0;
        int dirs[5] = {-1, 0, 1, 0, -1};
        function<int(int, int)> dfs = [&](int i, int j) {
            int ok = grid1[i][j];
            grid2[i][j] = 0;
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid2[x][y]) {
                    ok &= dfs(x, y);
                }
            }
            return ok;
        };
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid2[i][j]) {
                    ans += dfs(i, j);
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private final int[] dirs = {-1, 0, 1, 0, -1};
    private int[][] grid1;
    private int[][] grid2;
    private int m;
    private int n;

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        m = grid1.length;
        n = grid1[0].length;
        this.grid1 = grid1;
        this.grid2 = grid2;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid2[i][j] == 1) {
                    ans += dfs(i, j);
                }
            }
        }
        return ans;
    }

    private int dfs(int i, int j) {
        int ok = grid1[i][j];
        grid2[i][j] = 0;
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid2[x][y] == 1) {
                ok &= dfs(x, y);
            }
        }
        return ok;
    }
}