题目描述
思路解析动画文字版
记住「从边界陆地往里 DFS 标记可达 → 剩下没标记的陆地就是飞地」,下面逐帧套它。
第一步,沿着最外面一圈走一遍。每碰到一个边界上的陆地,就从它钻进去,把所有能连通的陆地都标成「能走到边界」。
边界格 (0, 0) 是陆地(紫),说明这块陆地能走到边界。从它钻进去,把连着的陆地全标蓝(能出去)。
从 (0, 0) 看四周:往下、右也是陆地,把它们一并标成「能出去」(蓝)、继续往里走。
边界格 (0, 1) 也是陆地,不过它刚才已经被同一片连通区灌到、标蓝了,不必再灌,看下一个。
检查边界格 (0, 2):是海不是陆地,没什么可灌的,继续看下一个边界格。
检查边界格 (0, 3):是海不是陆地,没什么可灌的,继续看下一个边界格。
边界格 (0, 4) 是陆地(紫),说明这块陆地能走到边界。从它钻进去,把连着的陆地全标蓝(能出去)。
从 (0, 4) 看四周:往下也是陆地,把它们一并标成「能出去」(蓝)、继续往里走。
检查边界格 (4, 0):是海不是陆地,没什么可灌的,继续看下一个边界格。
检查边界格 (4, 1):是海不是陆地,没什么可灌的,继续看下一个边界格。
检查边界格 (4, 2):是海不是陆地,没什么可灌的,继续看下一个边界格。
检查边界格 (4, 3):是海不是陆地,没什么可灌的,继续看下一个边界格。
检查边界格 (4, 4):是海不是陆地,没什么可灌的,继续看下一个边界格。
边界格 (1, 0) 也是陆地,不过它刚才已经被同一片连通区灌到、标蓝了,不必再灌,看下一个。
检查边界格 (2, 0):是海不是陆地,没什么可灌的,继续看下一个边界格。
检查边界格 (3, 0):是海不是陆地,没什么可灌的,继续看下一个边界格。
边界格 (1, 4) 也是陆地,不过它刚才已经被同一片连通区灌到、标蓝了,不必再灌,看下一个。
检查边界格 (2, 4):是海不是陆地,没什么可灌的,继续看下一个边界格。
检查边界格 (3, 4):是海不是陆地,没什么可灌的,继续看下一个边界格。
四条边走完。左上角那块(含 (0,0)、(0,1)、(1,0))和右上角那块(含 (0,4)、(1,4))都从边界灌到了,全标蓝。海格(灰点)挡住了继续扩散,所以只有这两块靠边的连通陆地被灌到、标蓝;中间那团没被灌到。
倒灌结束。接下来把整张网格再扫一遍:凡是陆地、却没被标蓝的,就是怎么走都出不去的飞地,标绿、计数。
(2, 2) 是陆地,可它没被标蓝,说明从边界灌不到它、它也走不到边界,是飞地(绿)。飞地计数累加到 1。
(2, 3) 是陆地,可它没被标蓝,说明从边界灌不到它、它也走不到边界,是飞地(绿)。飞地计数累加到 2。
(3, 2) 是陆地,可它没被标蓝,说明从边界灌不到它、它也走不到边界,是飞地(绿)。飞地计数累加到 3。
整张网格扫完,绿色的飞地一共 3 格,这就是答案。回头看:从边界倒灌标记一遍 O(mn)、再扫一遍计数 O(mn),整体就是 O(mn)。
边界:全内陆都算飞地;全挨边则 0;全海则 0。
两个追问:与「被围绕的区域」同一套倒灌思路;BFS/并查集也可。
参考代码
from typing import Listclass Solution: def numEnclaves(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def flood(sr: int, sc: int) -> None: # 显式栈迭代 DFS,避免大网格递归爆栈 stack = [(sr, sc)] grid[sr][sc] = 0 while stack: r, c = stack.pop() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1: grid[nr][nc] = 0 stack.append((nr, nc)) # 从四条边上的每个陆地倒灌 for r in range(m): for c in (0, n - 1): if grid[r][c] == 1: flood(r, c) for c in range(n): for r in (0, m - 1): if grid[r][c] == 1: flood(r, c) return sum(sum(row) for row in grid)复杂度
- 时间：O(m·n)，边界 DFS 每个陆地格最多被访问一次,最后求和再扫一遍整张网格,都是格子总数级
- 空间：O(m·n)，迭代用的显式栈最坏(整张几乎全是连通陆地)能压到格子总数级;没有额外开 visited 数组
易错点
面试追问把动画讲成自己的话
追问这题和「被围绕的区域」(把被围的 O 变 X)是不是一类?
追问能不能用 BFS 或并查集做?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二进制矩阵中的最短路径
LeetCode 1091 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题