02.6.2.4 岛屿与搜索类
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.2 经典回溯题型
02.6.2.4-001 岛屿数量(LC 200)网格 DFS 怎么做?
一句话结论
扫描网格,遇到未访问的陆地计数 +1,从该格 DFS/BFS 把连通陆地全部标记;每个连通块对应一座岛;标记后不再撤销。
概念解释
- 连通块:四方向相连的陆地。
- 计数:扫描遇到的新块起点。
原理流程
- 遍历每个格子。
- 未访问陆地 → 计数并洪水填充。
- 填充标记整座岛。
代码 / 示例
void dfs(char[][] g, int i, int j) {
if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == '0') return;
g[i][j] = '0';
for (int[] d : DIRS) dfs(g, i + d[0], j + d[1]);
}
// 外层:if (g[i][j]=='1') { count++; dfs(...); }
常见误区
- 误区:只判左右不判上下;正解:四方向齐全。
- 误区:DFS 后撤销陆地标记;正解:连通块标记永久保留。
追问
- Q:复杂度? A:O(mn),每格访问一次。
- Q:能用 BFS 吗? A:能,队列层序填充连通块。
02.6.2.4-002 岛屿最大面积(LC 695)怎么求?
一句话结论
每座岛 DFS 时累计格子数,返回连通块面积;扫描过程中维护最大面积;与岛屿数量框架一致,多一个面积累加返回值。
概念解释
- 面积:连通陆地格数。
- 返回值:本子树面积。
原理流程
- 起点陆地 DFS。
- 每格面积 1 + 四方向递归面积。
- 更新全局最大值。
代码 / 示例
int area(char[][] g, int i, int j) {
if (越界 || g[i][j] == '0') return 0;
g[i][j] = '0';
return 1 + area(g,i-1,j) + area(g,i+1,j) + area(g,i,j-1) + area(g,i,j+1);
}
常见误区
- 误区:面积只计起点;正解:递归累加整座岛。
- 误区:标记前先统计;正解:访问即标记防重复计数。
追问
- Q:空网格最大面积? A:0。
- Q:BFS 怎么计面积? A:出栈/出队一个格计数 +1。
02.6.2.4-003 被围绕的区域(LC 130)为什么反向 DFS?
一句话结论
边界上的 O 不会被围绕,先从边界 O DFS 标记所有与边界连通的 O;遍历结束后,未标记的内部 O 改为 X,标记过的恢复为 O;反向标记避免逐个判断是否被包围。
概念解释
- 围绕:四周被 X 封闭的内部 O。
- 反向:先保边界连通 O。
原理流程
- 四边遍历 O 起点 DFS 标记。
- 未标记 O 改 X。
- 标记位恢复 O。
代码 / 示例
// 边界 O → 标记为 '#'
// 遍历:'#' 恢复 'O',其余 'O' 改 'X'
常见误区
- 误区:从内部 O 开始 DFS 判断包围;正解:反向从边界更简单。
- 误区:标记字符与原字符冲突;正解:用临时标记
#区分。
追问
- Q:复杂度? A:O(mn)。
- Q:四个边界都要扫吗? A:是,上下左右边的 O 都可能连通内部。
02.6.2.4-004 腐烂橘子(LC 994)多源 BFS 怎么做?
一句话结论
初始所有腐烂橘子入队,多源同时层序扩散;每层记时间,新鲜橘子被感染后入队;统计剩余新鲜数,全部感染返回层数,否则 -1。
概念解释
- 多源 BFS:多个起点同时扩散。
- 层序:层数即经过分钟数。
原理流程
- 统计新鲜数,腐烂橘入队。
- 逐层感染邻居。
- 新鲜归零返回层数。
代码 / 示例
while (!q.isEmpty() && fresh > 0) {
int size = q.size();
for (int k = 0; k < size; k++) {
// 出队,感染四方向新鲜橘,入队,fresh--
}
minutes++;
}
return fresh == 0 ? minutes : -1;
常见误区
- 误区:单源逐个腐烂;正解:所有初始烂橘同时扩散,需一次性入队。
- 误区:层号与分钟错位;正解:每处理完一层时间 +1。
追问
- Q:复杂度? A:O(mn)。
- Q:为什么用 BFS 不用 DFS? A:求最短扩散时间,层序 BFS 最合适。
02.6.2.4-005 填海造陆最大岛屿(LC 827)怎么做?
一句话结论
先给每座岛编号并统计面积;再枚举每个海洋格,把四方向相邻不同岛屿面积求和 +1,取最大;无海洋格时返回最大岛面积。
概念解释
- 岛屿编号:区分连通块。
- 海洋填陆:连接相邻岛。
原理流程
- DFS 编号并算各岛面积。
- 扫海洋格收集相邻岛编号。
- 面积合并求最大。
代码 / 示例
// 岛 id 矩阵 + 面积数组;海洋格邻岛去重后 sum[area[id]] + 1
常见误区
- 误区:相邻同岛重复计算;正解:邻岛编号去重。
- 误区:填海格自身不算面积;正解:+1 计入新陆地。
追问
- Q:复杂度? A:O(mn) 两遍扫描。
- Q:无海洋时答案? A:原最大岛屿面积。
02.6.2.4-006 岛屿周长(LC 463)怎么算?
一句话结论
每块陆地贡献 4 条边,每与一块相邻陆地抵消 2 条边(相邻边双方各减一条);遍历陆地统计 4×陆地块数 - 2×相邻边数。
概念解释
- 边贡献:陆地初始 4 边。
- 相邻抵消:共享边不算周长。
原理流程
- 数陆地格数。
- 数向右/向下相邻对数。
- 公式计算周长。
代码 / 示例
for (int i=0;i<m;i++) for (int j=0;j<n;j++)
if (g[i][j]==1) { peri += 4; if (右/下为陆地) peri -= 2; }
常见误区
- 误区:相邻抵消只减一次;正解:共享边两侧各减 1,共减 2。
- 误区:四方向都判相邻导致重复;正解:只判右、下避免重复计数。
追问
- Q:复杂度? A:O(mn)。
- Q:DFS 也能算周长吗? A:能,统计边界为水/越界的边数。
02.6.2.4-007 封闭岛屿数量(LC 1254)怎么判断?
一句话结论
从边界陆地 DFS 排除所有触边连通块;剩余未访问陆地都是被水封闭的岛,计数;与被围绕区域思路一致,反向标记边界连通。
概念解释
- 封闭:不接触网格边界。
- 排除:边界连通块不算封闭。
原理流程
- 边界陆地 DFS 标记。
- 扫内部未访问陆地计数。
- 每座内部岛 DFS 标记。
代码 / 示例
边界 DFS 标记 → 内部未访问陆地 count++ 并填充
常见误区
- 误区:触边岛也算封闭;正解:接触边界即不封闭。
- 误区:只看单格是否靠边;正解:连通到边界即排除。
追问
- Q:与岛屿数量区别? A:排除触边连通块。
- Q:复杂度? A:O(mn)。
02.6.2.4-008 网格连通块(水域大小)怎么统计?
一句话结论
通用连通块模板:扫描未访问的目标格子,DFS/BFS 统计块大小,记录每个连通块;目标类型按题意(水、陆地、相同值);标记访问后不撤销。
概念解释
- 连通块:同类型相邻格子集合。
- 模板:扫描起点 + 洪水填充。
原理流程
- 遍历网格找未访问目标格。
- 填充并统计块。
- 记录块大小。
代码 / 示例
// 模板:起点 → DFS 标记 → 累计大小 → 加入结果
常见误区
- 误区:不同类型格子混在一块;正解:只连通相同类型。
- 误区:漏统计孤立单格;正解:单格也是连通块。
追问
- Q:八方向连通怎么改? A:方向数组扩到 8 个偏移。
- Q:连通块数量与大小分别存吗? A:按题意计数或收集大小列表。
02.6.2.4-009 网格 DFS 四方向与 visited 怎么写?
一句话结论
方向数组存上下左右偏移;递归先判越界与访问状态,再标记访问,四方向深入;visited 可独立布尔矩阵或原地修改格子值。
概念解释
- 方向数组:统一遍历邻居。
- 访问标记:防重复入格。
原理流程
- 越界/已访问返回。
- 标记当前格。
- 四方向递归。
代码 / 示例
int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
常见误区
- 误区:方向数组漏方向;正解:四方向齐全。
- 误区:先递归后标记;正解:进入即标记防重复。
追问
- Q:visited 用矩阵还是原地改? A:不改原数据用矩阵,可修改则原地省空间。
- Q:八方向要改什么? A:DIRS 加四个斜向偏移。
02.6.2.4-010 原地修改替代 visited 有什么利弊?
一句话结论
把访问过的目标格改成标记值(如 0、#)省去 visited 矩阵,空间 O(1) 额外;代价是修改原网格,需要保留原值时不能用;回溯型题目还要恢复原值。
概念解释
- 原地标记:改格子值。
- 省空间:免 visited。
原理流程
- 进入格子改标记值。
- 邻居看到标记即跳过。
- 需要还原时记录原值。
代码 / 示例
g[i][j] = '0'; // 原地标记已访问
常见误区
- 误区:题目要求保留原网格还原地改;正解:用独立 visited。
- 误区:标记值与合法值冲突;正解:选不会出现的字符。
追问
- Q:原地改能恢复吗? A:连通块题通常不需恢复;回溯题需保存原值。
- Q:空间复杂度怎么报? A:原地改辅助 O(1),visited 矩阵 O(mn)。
02.6.2.4-011 BFS 层序与距离怎么记录?
一句话结论
队列存坐标,入队时记录距离(或按层号递增);多源 BFS 初始源点距离 0;出队扩展邻居时距离 +1;层序处理保证首次到达即最短距离。
概念解释
- 距离:到源点步数。
- 层号:BFS 层数。
原理流程
- 源点入队距离 0。
- 出队扩展,邻居距离 +1 入队。
- 已访问不再入队。
代码 / 示例
Queue<int[]> q = new ArrayDeque<>();
// q.offer(new int[]{i,j,0});
// 邻居:new int[]{x,y,d+1}
常见误区
- 误区:同一格多次入队更新距离;正解:首次到达最短,标记后不再入队。
- 误区:层号与距离错位;正解:按层处理或随节点存距离。
追问
- Q:为什么 BFS 给最短距离? A:边权相同,层序先到即最短。
- Q:距离矩阵怎么初始化? A:未达设 -1,源点 0。
02.6.2.4-012 网格最短路径(迷宫)怎么搜?
一句话结论
可通行格子上 BFS,队列存坐标与当前步数,首次到达终点即最短路径;带障碍/权重时按题意调整;DFS 枚举所有路径不能直接给最短。
概念解释
- 最短路径:步数最少。
- BFS:等权边层序最优。
原理流程
- 起点入队标记。
- 扩展可通行邻居。
- 到终点返回步数。
代码 / 示例
// 队列存 (i,j,steps);访问标记;终点即返回
常见误区
- 误区:用 DFS 找最短;正解:DFS 需枚举全部路径,BFS 更直接。
- 误区:终点不提前返回;正解:BFS 首次到达即最短。
追问
- Q:迷宫允许回头吗? A:visited 防重复入队即可。
- Q:带权迷宫用什么? A:Dijkstra,BFS 不再适用。
02.6.2.4-013 网格单词搜索与岛屿 DFS 有何区别?
一句话结论
岛屿 DFS 标记后不撤销,统计连通块;单词搜索是回溯,路径标记用完撤销,允许其他路径再走该格;两者网格遍历框架相同,现场恢复策略不同。
概念解释
- 连通型:永久标记。
- 回溯型:标记撤销。
原理流程
- 同:越界判断 + 方向遍历。
- 异:连通不复位,回溯复位。
- 收集目标不同。
代码 / 示例
岛屿:g[i][j]='0' 后不恢复
单词:标记 → 递归 → 恢复原值
常见误区
- 误区:把单词搜索当连通块不撤销;正解:会堵死其他路径。
- 误区:岛屿题撤销标记;正解:重复访问同一连通块。
追问
- Q:怎么判断该撤销? A:看格子是否需要被其他分支再次使用。
- Q:两类题复杂度? A:均 O(mn) 量级,回溯类带单词长度分支。
02.6.2.4-014 洪水填充(LC 733)怎么做?
一句话结论
从起点像素出发,把与起点同色的连通块替换为新颜色;DFS/BFS 四方向扩展,颜色相同才填充;已填充格不再重复处理。
概念解释
- 洪水填充:同色连通块换色。
- 起点色:比较基准。
原理流程
- 记录起点原颜色。
- 同色邻居递归填充。
- 异色/越界跳过。
代码 / 示例
void fill(int[][] g, int i, int j, int old, int nw) {
if (越界 || g[i][j] != old) return;
g[i][j] = nw;
for (int[] d : DIRS) fill(g, i+d[0], j+d[1], old, nw);
}
常见误区
- 误区:新颜色等于旧颜色仍递归;正解:先判断避免死循环。
- 误区:只填充起点;正解:扩展整个连通块。
追问
- Q:复杂度? A:O(mn)。
- Q:与岛屿数量关系? A:同一连通块模板。
02.6.2.4-015 岛屿数量的并查集视角是什么?
一句话结论
把相邻陆地合并到同一集合,最后统计集合个数;遍历相邻陆地 union,根节点计数;并查集适合动态连通性,静态网格 DFS/BFS 更直接。
概念解释
- 并查集:合并连通块。
- 计数:不同根个数。
原理流程
- 陆地初始化各自集合。
- 相邻陆地 union。
- 统计不同根。
代码 / 示例
右/下相邻陆地 → union;最后 count 不同 parent
常见误区
- 误区:水格也计入集合;正解:只对陆地建集。
- 误区:重复 union 影响计数;正解:并查集幂等,不影响最终根。
追问
- Q:并查集复杂度? A:近似 O(mn·α)。
- Q:什么场景选并查集? A:动态加边、连通分量合并查询。
02.6.2.4-016 网格边界与越界判断怎么写稳?
一句话结论
统一在递归/队列入口判断行列范围 0<=i<m、0<=j<n,越界直接返回;判断先于格子内容访问;边界格子作为合法起点单独扫描。
概念解释
- 越界:下标超出矩阵。
- 入口判断:统一兜底。
原理流程
- 取 m、n。
- 入口判范围。
- 再访问格子值。
代码 / 示例
if (i < 0 || i >= m || j < 0 || j >= n) return;
常见误区
- 误区:先取
g[i][j]再判越界;正解:先判范围防异常。 - 误区:行列维度写反;正解:m 为行数,n 为列数。
追问
- Q:单行/单列网格要注意什么? A:边界判断同样有效,方向邻居自然越界。
- Q:空网格怎么处理? A:m 或 n 为 0 直接返回。
02.6.2.4-017 回溯与洪水填充怎么区分使用?
一句话结论
目标是统计/修改连通块整体,标记后不撤销,用洪水填充;目标是枚举路径方案、格子可被不同方案复用,用回溯并撤销;先判断结果是否需要保留多路径。
概念解释
- 填充:连通块一次性处理。
- 回溯:多路径枚举。
原理流程
- 判断是否有多条候选路径。
- 单块填充 → DFS/BFS 不撤销。
- 多方案 → 回溯撤销。
代码 / 示例
岛屿/填充:不复位;单词搜索/路径:复位
常见误区
- 误区:所有网格题都撤销;正解:连通块统计无需撤销。
- 误区:填充题保留路径;正解:只需要块信息。
追问
- Q:迷宫找一条路径用哪种? A:回溯 DFS,标记可在找到后保留。
- Q:连通块求所有块大小用哪种? A:洪水填充。
02.6.2.4-018 连通块统计模板包含哪些步骤?
一句话结论
模板:外层扫描每个格子 → 未访问目标格则启动 DFS/BFS → 填充标记并累计信息 → 结果计数/收集;方向数组与越界判断复用同一套。
概念解释
- 外层:找起点。
- 内层:填充统计。
- 复用:方向与标记逻辑。
原理流程
- 扫描网格。
- 起点启动填充。
- 更新结果。
代码 / 示例
for i,j: if (目标且未访问) { 计数/收集; dfs(i,j); }
常见误区
- 误区:外层漏扫边界格;正解:全矩阵遍历。
- 误区:填充内重复判断起点;正解:内层只处理邻居。
追问
- Q:模板能套哪些题? A:岛屿、水域、连通相同值、包围区域。
- Q:返回信息怎么扩展? A:DFS 返回面积/边界/种类等聚合值。
02.6.2.4-019 网格题复杂度 m×n 口径怎么报?
一句话结论
每个格子最多访问一次,时间 O(mn);DFS 递归栈最坏 O(mn)(蛇形全连通),BFS 队列 O(mn);标记矩阵 O(mn),原地改则辅助 O(1);输出结果按题意单列。
概念解释
- 访问次数:每格常数次。
- 栈/队列:最坏存整网。
原理流程
- 估每格访问次数。
- 加栈/队列峰值。
- 标记空间单列。
代码 / 示例
时间 O(mn);递归栈 O(mn);visited O(mn)(原地改 O(1))
常见误区
- 误区:递归栈按 O(1) 报;正解:全连通蛇形深度可达 mn。
- 误区:BFS 队列空间忽略;正解:层宽峰值可达 O(mn)。
追问
- Q:网格很大递归会溢出吗? A:会,深网格改显式栈 BFS/DFS。
- Q:多源 BFS 复杂度? A:仍 O(mn)。
02.6.2.4-020 网格搜索常见错误有哪些?
一句话结论
高频错误:方向不全、越界判断在后、标记不撤销或误撤销、起点漏扫、颜色/类型比较错误、多源未同时入队;按方向数组、入口判断、标记策略、外层扫描逐项排查。
概念解释
- 遍历:方向与边界。
- 标记:撤销策略。
- 扫描:起点完整。
原理流程
- 核对方向数组与越界。
- 确认标记是否复位。
- 全网格扫描起点。
代码 / 示例
排查:DIRS / 越界顺序 / 标记策略 / 外层扫描 / 类型比较 / 多源入队
常见误区
- 误区:小网格通过就认为方向齐全;正解:补角落与单行用例。
- 误区:把水格当陆地处理;正解:比较当前格子类型。
追问
- Q:结果多块先查什么? A:标记是否未复位或起点重复。
- Q:结果漏块先查什么? A:外层扫描范围与类型判断。