‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者1.dfs版#includeiostream #includevector #includealgorithm #includequeue using namespace std; vectorvectorintedge; long long sum 0; int dx[4] { 1,-1,0,0 }; int dy[4] { 0,0,1,-1 }; int N, M; void dfs(int i, int j) { int x i; int y j; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx N ny 1 ny M edge[nx][ny] 1) { edge[nx][ny] 0; dfs(nx, ny); } } } int main() { cin N M; edge.resize(N 1, vectorint(M 1, 0)); for (int i 1; i N; i) { for (int j 1; j M; j) { cin edge[i][j]; } } for (int i 1; i N; i) { for (int j 1; j M; j) { if (edge[i][j] 1) { sum; dfs(i, j); } } } cout sum endl; return 0; }用 DFS 解决“岛屿数量问题”从代码到思路一次讲透这类题在数据结构与算法里非常经典本质就是在一个二维网格中统计连通块的数量。你这段代码写的是最标准的解法之一——DFS深度优先搜索。很多人一开始只是“会写”但不太清楚为什么这样写这篇文章就带你把这段代码彻底理解。一、问题本质给你一个 N×M 的网格1 表示陆地0 表示水要求统计有多少个“岛屿”连通的 1举个例子1 1 0 0 1 0 0 1 0 0 1 1这里有 3 个岛屿。二、核心思路非常重要一句话总结遇到一个 1就把整个连通块“淹掉”什么意思扫描整个地图遇到一个 1 → 说明发现新岛屿用 DFS 把和它连在一起的所有 1 全部改成 0岛屿数量 1三、DFS 在这里干了什么来看你的代码void dfs(int i, int j) { int x i; int y j; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx N ny 1 ny M edge[nx][ny] 1) { edge[nx][ny] 0; dfs(nx, ny); } } }关键点拆解1. 四个方向int dx[4] { 1,-1,0,0 }; int dy[4] { 0,0,1,-1 };表示下 上 右 左2. 向四周扩展int nx x dx[i]; int ny y dy[i];就是在找相邻的格子。3. 判断是否合法nx 1 nx N ny 1 ny M防止越界。4. 判断是否是陆地edge[nx][ny] 1只有是 1 才继续扩展。5. 标记已访问edge[nx][ny] 0;这一步非常关键防止重复访问否则会死循环四、主函数逻辑for (int i 1; i N; i) { for (int j 1; j M; j) { if (edge[i][j] 1) { sum; dfs(i, j); } } }逻辑解释遍历每个格子如果是 1说明发现一个新岛sum用 DFS 把整个岛“清空”五、完整执行流程重点理解假设某个点是 1发现一个岛 → sum然后DFS 把整个连通区域全部变成 0这样同一个岛只会被统计一次后续不会重复计数六、时间复杂度O(N × M)原因每个点最多访问一次DFS 不会重复访问七、空间复杂度递归 DFS最坏 O(N × M)比如整个图都是 1会递归很深。八、常见错误1. 忘记标记访问edge[nx][ny] 0;会导致无限递归。2. 越界没判断nx 1 nx N必须写3. 没有在主循环中判断 1if(edge[i][j] 1)否则会重复 DFS。九、可以优化的点你的代码其实可以更规范一点比如优化起点也要清零if (edge[i][j] 1) { sum; edge[i][j] 0; dfs(i, j); }避免重复访问当前点。十、一句话总结DFS 在网格问题中的本质就是从一个点出发把整个连通块全部“吃掉”。bfs版#includeiostream #includevector #includealgorithm #includequeue using namespace std; vectorvectorintedge; long long sum 0; int dx[4] { 1,-1,0,0 }; int dy[4] { 0,0,1,-1 }; int N, M; queue pairint, int q; void bfs(int i, int j) { while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx N ny 1 ny Medge[nx][ny]1) { edge[nx][ny] 0; q.push({ nx,ny }); } } } } int main() { cin N M; edge.resize(N 1, vectorint(M 1, 0)); for (int i 1; i N; i) { for (int j 1; j M; j) { cin edge[i][j]; } } for (int i 1; i N; i) { for (int j 1; j M; j) { if (edge[i][j] 1) { sum; q.push({ i,j }); bfs(i, j); } } } cout sum endl; return 0; }用 BFS 解决“岛屿数量问题”从代码细节到思路彻底吃透在上一种写法中我们用 DFS 做了连通块统计这一篇我们用BFS广度优先搜索来解决同一个问题并把你这段代码彻底讲清楚。很多同学写 BFS 能跑通但对“为什么这么写”理解不够这里我们把逻辑拆开讲清楚。一、问题本质再回顾给你一个二维网格1 表示陆地0 表示水目标统计有多少个“岛屿”上下左右连通的 1二、BFS 的核心思想一句话总结从一个点出发一层一层把整个连通块全部扩展完和 DFS 的区别DFS一条路走到黑递归BFS一层一层扩展队列三、你的代码结构分析1. 方向数组int dx[4] { 1,-1,0,0 }; int dy[4] { 0,0,1,-1 };表示四个方向下 上 右 左2. BFS函数void bfs(int i, int j) { while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 1 nx N ny 1 ny M edge[nx][ny] 1) { edge[nx][ny] 0; q.push({ nx,ny }); } } } }四、BFS 执行过程详解第一步发现新岛屿if (edge[i][j] 1) { sum; q.push({ i,j }); bfs(i, j); }含义发现一个 1 → 新岛屿 → sum然后把这个点丢进队列开始“扩散”第二步队列扩展队列[(起点)]进入 BFS取出一个点向四个方向扩展找到新的 1 → 入队第三步逐层扩展举个例子1 1 0 1 0 0过程(1,1) 入队 ↓ 扩展到 (1,2)、(2,1) ↓ 再扩展它们的邻居 ↓ 直到整个岛屿全部变成 0五、一个关键问题你这段代码的小坑你现在的代码q.push({ i,j }); bfs(i, j);但你没有把起点标记为 0会发生什么起点仍然是 1虽然一般不会死循环但逻辑不严谨有重复访问风险正确写法必须改if (edge[i][j] 1) { sum; edge[i][j] 0; // 关键先标记 q.push({ i,j }); bfs(i, j); }六、为什么一定要“先标记”核心原因防止一个点被多次加入队列如果不标记可能从不同方向重复访问队列变大效率变差七、时间复杂度O(N × M)原因每个点最多进队一次每条边最多访问一次八、空间复杂度O(N × M)最坏情况整个图都是 1队列会存很多节点九、DFS vs BFS快速对比项目DFSBFS实现递归队列访问方式一条路走到底一层一层扩展空间递归栈队列使用场景连通块、回溯最短路径、层序十、代码优化版本推荐写法void bfs(int i, int j) { queuepairint,int q; q.push({i,j}); edge[i][j] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 1 nx N ny 1 ny M edge[nx][ny] 1) { edge[nx][ny] 0; q.push({nx, ny}); } } } }优点队列局部化更安全逻辑更清晰不依赖全局变量十一、一句话总结BFS 本质就是从一个点出发用队列一层一层把整个连通块全部“扩散清空”。