C++递归算法处理岛屿问题详解
面对二维网格中的连通区域判定，如求岛屿数量或周长，递归（DFS）是核心解题思路。本文将拆解C++递归模板，演示如何通过原地标记法避免重复计算，并分别解决“岛屿的数量”和“岛屿的周长”两道经典题目。
岛屿问题的递归模型构建
岛屿问题通常在二维数组环境中模拟，其中 1 代表陆地，0 代表海洋。所谓“岛屿”，即被水包围的陆地集合。这类问题本质上是图论中的连通分量搜索，最适合使用递归的深度优先搜索（DFS）来解决。
在处理每一个陆地坐标时，我们需要检查其上下左右四个方向的相邻格子是否也是陆地，若是则继续深入。一个关键挑战在于避免同一位置被多次递归调用导致的死循环和性能下降。解决方案是引入“备忘录”机制——直接在原二维数组中修改已访问陆地的状态。
第1步：编写通用DFS递归框架
以下是处理此类网格问题的标准递归模板。该函数负责判断边界、执行操作并标记当前节点：
public void dfs(char[][] grid, int m, int n){
// 1. 检查越界或该位置已被访问过
if(isBeyond(grid, m, n) || grid[m][n] == '2'){
return;
}
// 2. 针对具体业务的操作（此处留空，视题目而定）
// 3. 记录已经遍历过的位置：将'1'修改为'2'
grid[m][n] = '2';
// 4. 递归遍历上下左右四个方向
dfs(grid, m-1, n); // 上
dfs(grid, m+1, n); // 下
dfs(grid, m, n-1); // 左
dfs(grid, m, n+1); // 右
}
// 辅助函数：检测坐标是否越界
boolean isBeyond(char[][] grid, int m, int n){
if(m < 0 || m>=grid.length || n<0 || n>=grid[0].length){
return true;
}
return false;
}
上述代码中的备忘录策略非常高效：通过直接将已访问的陆地值从 1 改为 2，既完成了标记任务，又节省了额外的哈希表或布尔数组空间。如果不在递归入口处拦截 grid[m][n] == '2'，相同节点会被反复进入，显著增加时间复杂度。
实战一：计算岛屿的数量
题目目标： 统计给定二维数组中包含的完整岛屿个数。
解题逻辑：
- 遍历整个二维网格的所有坐标点。
- 一旦发现值为
1的陆地，说明发现了一个新的岛屿，计数器加一。 - 立即调用
dfs函数将该岛屿相连的所有陆地都标记为2，防止后续循环再次计数。
第2步：实现岛屿计数完整代码
主函数通过双重循环扫描网格，找到未访问的陆地后即触发清洗操作：
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int ans = 0;
for(int i=0; i=grid.length || n<0 || n>=grid[0].length){
return true;
}
return false;
}
} 实战二：计算岛屿的周长
题目前提： 输入保证只有一个连通岛屿。
核心分析：
岛屿的周长由陆地与外部环境的交界线构成。对于任意一块陆地方块，其每一条边如果满足以下任一条件，就会对总周长贡献 +1：
- 该边的相邻格子是海洋（值为
0）。 - 该边的相邻位置超出了二维数组的边界。
基于此原理，我们可以从唯一的陆地块出发进行DFS搜索。每次遇到非陆地（海洋）或越界时，返回1；如果已经访问过当前块，则返回0（不计入周长）。
第3步：实现周长计算代码
class Solution {
// 遍历所有陆地，累加每个方块的贡献度
public int islandPerimeter(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 因为保证只有一个岛屿，找到第一个陆地即可开始计算
for(int i=0; i grid.length || n > grid[0].length){
return true;
}
return false;
}
} 总结
以上关于C++递归算法处理岛屿问题的详细内容，更多关于C++岛屿问题算法优化的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
