题目描述
思路解析动画文字版
记牢这一句:grid2 的一座岛屿要成为子岛屿,岛内每一个格子在 grid1 里都必须是陆地,一个都不能踩空。下面从左上角开始,一座一座岛屿地查。
先看 grid1 · 大陆地图：这是 grid1,把它当成一张大陆底图。绿色是陆地 1,浅蓝是水 0。它本身不数岛屿,它的作用是当一把尺子:grid2 的岛屿想过关,岛内每个格子都得落在 grid1 的绿色陆地上。你先记住它绿色陆地的分布,左上角有一小片,右下角整行连成一片。
再看 grid2 · 要数岛屿的图：这是 grid2,它才是我们要数岛屿的主角。绿色陆地一眼看去分成三块:左上角一块 4 格,右下角一块 2 格,左下角一块 2 格。接下来的活儿就是:把这三块岛屿逐一拿去和 grid1 比对,看哪些整块都被 grid1 的陆地托住。
工作网格 · 陆地格写上 grid1 的托底值：为了少画一张图,把两张网格合到一起看。舞台这张网格的形状就是 grid2:凡是 grid2 的陆地格,我在上面直接写它在 grid1 的托底值,1 表示底下有陆地稳稳托着,0 表示底下是水、是个洞;grid2 的水格写一个点,不参与数岛。左上那块里 (0,2) 写着 0,已经能看出它脚下踩空,不过我们仍按算法一步步走过去确认。
外层扫描 · 发现第一座岛屿,起点 (0,0)：外层循环从左上角开始扫 grid2,第一个碰到的陆地是 (0,0),以它为起点发起一次 DFS,把整座岛屿走遍。约定一个记号 ok,一路把岛内每格在 grid1 的值按位与进去,起点这格 grid1 是 1,ok 先记成 1。
踏稳起点 (0,0) · grid1 托底 = 1：正式踏上起点 (0,0),把它沉掉防止回头重数。低头看脚下写的数字是 1,说明它在 grid1 也是陆地,托底没问题。接着按上右下左四个方向,找相连的陆地继续往里钻。
从 (0,0) 看四邻 · 右边是陆地：站在 (0,0),按上右下左依次看四个邻居。上边出界,右边 (0,1) 是陆地、还没走过,那就先钻进去。DFS 的规矩就是这样:每到一格,先把一条路走到底,再回头处理别的分支。
走入 (0,1) · grid1 托底 = 1：沿着相连的陆地走到 (0,1),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。到目前为止这座岛屿每一格都踩在陆地上,ok 依然是 1。
从 (0,1) 看四邻 · 右边和下边都是陆地：来到 (0,1),它有两条路可走:右边 (0,2) 是陆地,下边 (1,1) 也是陆地。按上右下左的顺序,先钻右边那条,把它彻底走完再回来处理下边。正是这一步之后,我们会撞上那个藏在右边的洞。
踏到 (0,2) · grid1 是水,发现洞!：顺着相连陆地走到 (0,2),低头一看脚下写着 0,这个位置在 grid1 是水。按位与遇到 0,ok 立刻被压成 0,这座岛屿从此注定不是子岛屿。但注意:算法不会马上收手,还要把这块剩下的陆地都走遍沉掉,免得残格被后面误当成新岛屿。
走入 (1,1) · grid1 托底 = 1：沿着相连的陆地走到 (1,1),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。不过之前已经踩过洞了,ok 已经是 0,这一格是 1 也救不回来,继续把剩余格子走完。
第一座岛屿结算 · 踩到洞,作废：这座岛屿一共 4 个格子,可惜其中 (0,2) 那格在 grid1 是水,ok 早被压成了 0。哪怕别的格子都托底,只要有这一个洞,整块就不算子岛屿。把它标成灰色、洞那格标红,已确认子岛屿数仍然是 0,不加。
外层扫描 · 发现第二座岛屿,起点 (2,3)：外层扫描继续往后走,前面走过的格子都已经沉掉了,现在碰到还没处理的陆地 (2,3),这是第二座岛屿的起点,又发起一次 DFS。ok 重新从起点的 grid1 值 1 开始。
踏稳起点 (2,3) · grid1 托底 = 1：正式踏上起点 (2,3),把它沉掉防止回头重数。低头看脚下写的数字是 1,说明它在 grid1 也是陆地,托底没问题。接着按上右下左四个方向,找相连的陆地继续往里钻。
走入 (3,3) · grid1 托底 = 1：沿着相连的陆地走到 (3,3),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。到目前为止这座岛屿每一格都踩在陆地上,ok 依然是 1。
第二座岛屿结算 · 全程托底,子岛屿 +1：这座岛屿走完了,一共 2 个格子,每一个在 grid1 里都是陆地,ok 始终是 1。它就是一个子岛屿,把它整块标成绿色,已确认子岛屿数加到 1。
外层扫描 · 发现第三座岛屿,起点 (3,0)：外层扫描继续往后走,前面走过的格子都已经沉掉了,现在碰到还没处理的陆地 (3,0),这是第三座岛屿的起点,又发起一次 DFS。ok 重新从起点的 grid1 值 1 开始。
踏稳起点 (3,0) · grid1 托底 = 1：正式踏上起点 (3,0),把它沉掉防止回头重数。低头看脚下写的数字是 1,说明它在 grid1 也是陆地,托底没问题。接着按上右下左四个方向,找相连的陆地继续往里钻。
走入 (3,1) · grid1 托底 = 1：沿着相连的陆地走到 (3,1),把它沉掉。脚下写着 1,在 grid1 里也是陆地,这一格托底稳当。到目前为止这座岛屿每一格都踩在陆地上,ok 依然是 1。
第三座岛屿结算 · 全程托底,子岛屿 +1：这座岛屿走完了,一共 2 个格子,每一个在 grid1 里都是陆地,ok 始终是 1。它就是一个子岛屿,把它整块标成绿色,已确认子岛屿数加到 2。
回放 · 两座绿岛过关,答案 2：三座岛屿全部查完。左上那块 4 格因为 (0,2) 踩了洞作废;右下和左下两块,每个格子都稳稳落在 grid1 的陆地上,是货真价实的子岛屿。数一数绿色的岛,一共 2 座,这就是答案。判定始终只看一条:岛内有没有哪个格子在 grid1 里是水。
边界想清:两边同为单陆地记 1、grid2 陆地而 grid1 是水记 0、一座岛里只要夹一个 grid1 的水就整块作废。
面试重点:逐块洪水填充按格判托底、可换编号或并查集、时间空间都是 O(m 乘 n)。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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])复杂度
- 时间：O(m·n)，m 行 n 列共 m 乘 n 个格子。外层扫一遍每个格子,每个陆地格被某次 DFS 恰好访问并沉掉一次,每格只看四个固定方向,都是常数操作,整体随格子总数线性增长
- 空间：O(m·n)，按峰值算。原地把 grid2 当访问标记不额外开表;递归栈深度最坏是一整块岛屿铺满整张网格时,栈里排到接近 m 乘 n 个格子。峰值就是 O(m·n),不随面积平方增长
易错点
面试追问把动画讲成自己的话
追问这题的核心判定到底是什么?
追问除了 DFS,还能怎么做?
追问为什么时间是线性,空间又是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
循环轮转矩阵
LeetCode 1914 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题