统计子岛屿 图解题解

这道题到底在问什么

输入

grid1=[[1,1,0,0],[0,1,0,0],[0,0,0,1],[1,1,1,1]], grid2=[[1,1,1,0],[0,1,0,0],[0,0,0,1],[1,1,0,1]]

输出

2

输入

grid1=[[1]], grid2=[[1]]

输出

1

最优解：一步一步想明白

1. 3记牢这一句:grid2 的一座岛屿要成为子岛屿,岛内每一个格子在 grid1 里都必须是陆地,一个都不能踩空。下面从左上角开始,一座一座岛屿地查。
2. 4底图:哪里有陆地这是 grid1,把它当成一张大陆底图。绿色是陆地 1,浅蓝是水 0。它本身不数岛屿,它的作用是当一把尺子:grid2 的岛屿想过关,岛内每个格子都得落在 grid1 的绿色陆地上。你先记住它绿色陆地的分布,左上角有一小片,右下角整行连成一片。
3. 5主角:数子岛屿这是 grid2,它才是我们要数岛屿的主角。绿色陆地一眼看去分成三块:左上角一块 4 格,右下角一块 2 格,左下角一块 2 格。接下来的活儿就是:把这三块岛屿逐一拿去和 grid1 比对,看哪些整块都被 grid1 的陆地托住。
4. 6目标:数出子岛屿为了少画一张图,把两张网格合到一起看。舞台这张网格的形状就是 grid2:凡是 grid2 的陆地格,我在上面直接写它在 grid1 的托底值,1 表示底下有陆地稳稳托着,0 表示底下是水、是个洞;grid2 的水格写一个点,不参与数岛。左上那块里 (0,2) 写着 0,已经能看出它脚下踩空,不过我们仍按算法一步步走过去确认。
5. 7第一座岛屿开工外层循环从左上角开始扫 grid2,第一个碰到的陆地是 (0,0),以它为起点发起一次 DFS,把整座岛屿走遍。约定一个记号 ok,一路把岛内每格在 grid1 的值按位与进去,起点这格 grid1 是 1,ok 先记成 1。
6. 8进入 (0,0)正式踏上起点 (0,0),把它沉掉防止回头重数。低头看脚下写的数字是 1,说明它在 grid1 也是陆地,托底没问题。接着按上右下左四个方向,找相连的陆地继续往里钻。
7. 9沿右侧深入站在 (0,0),按上右下左依次看四个邻居。上边出界,右边 (0,1) 是陆地、还没走过,那就先钻进去。DFS 的规矩就是这样:每到一格,先把一条路走到底,再回头处理别的分支。
8. 10进入 (0,1)沿着相连的陆地走到 (0,1),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。到目前为止这座岛屿每一格都踩在陆地上,ok 依然是 1。
9. 11先探右邻来到 (0,1),它有两条路可走:右边 (0,2) 是陆地,下边 (1,1) 也是陆地。按上右下左的顺序,先钻右边那条,把它彻底走完再回来处理下边。正是这一步之后,我们会撞上那个藏在右边的洞。
10. 12(0,2) 是洞顺着相连陆地走到 (0,2),低头一看脚下写着 0,这个位置在 grid1 是水。按位与遇到 0,ok 立刻被压成 0,这座岛屿从此注定不是子岛屿。但注意:算法不会马上收手,还要把这块剩下的陆地都走遍沉掉,免得残格被后面误当成新岛屿。
11. 13进入 (1,1)沿着相连的陆地走到 (1,1),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。不过之前已经踩过洞了,ok 已经是 0,这一格是 1 也救不回来,继续把剩余格子走完。
12. 14作废,不计数这座岛屿一共 4 个格子,可惜其中 (0,2) 那格在 grid1 是水,ok 早被压成了 0。哪怕别的格子都托底,只要有这一个洞,整块就不算子岛屿。把它标成灰色、洞那格标红,已确认子岛屿数仍然是 0,不加。
13. 15第二座岛屿开工外层扫描继续往后走,前面走过的格子都已经沉掉了,现在碰到还没处理的陆地 (2,3),这是第二座岛屿的起点,又发起一次 DFS。ok 重新从起点的 grid1 值 1 开始。
14. 16进入 (2,3)正式踏上起点 (2,3),把它沉掉防止回头重数。低头看脚下写的数字是 1,说明它在 grid1 也是陆地,托底没问题。接着按上右下左四个方向,找相连的陆地继续往里钻。
15. 17进入 (3,3)沿着相连的陆地走到 (3,3),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。到目前为止这座岛屿每一格都踩在陆地上,ok 依然是 1。
16. 18子岛屿数 = 1这座岛屿走完了,一共 2 个格子,每一个在 grid1 里都是陆地,ok 始终是 1。它就是一个子岛屿,把它整块标成绿色,已确认子岛屿数加到 1。
17. 19第三座岛屿开工外层扫描继续往后走,前面走过的格子都已经沉掉了,现在碰到还没处理的陆地 (3,0),这是第三座岛屿的起点,又发起一次 DFS。ok 重新从起点的 grid1 值 1 开始。
18. 20进入 (3,0)正式踏上起点 (3,0),把它沉掉防止回头重数。低头看脚下写的数字是 1,说明它在 grid1 也是陆地,托底没问题。接着按上右下左四个方向,找相连的陆地继续往里钻。
19. 21进入 (3,1)沿着相连的陆地走到 (3,1),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。到目前为止这座岛屿每一格都踩在陆地上,ok 依然是 1。
20. 22子岛屿数 = 2这座岛屿走完了,一共 2 个格子,每一个在 grid1 里都是陆地,ok 始终是 1。它就是一个子岛屿,把它整块标成绿色,已确认子岛屿数加到 2。
21. 23答案 = 2三座岛屿全部查完。左上那块 4 格因为 (0,2) 踩了洞作废;右下和左下两块,每个格子都稳稳落在 grid1 的陆地上,是货真价实的子岛屿。数一数绿色的岛,一共 2 座,这就是答案。判定始终只看一条:岛内有没有哪个格子在 grid1 里是水。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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])

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问