【C++】深度优先搜索3
·
【深度优先搜索3】本课导读
Go~
一、回顾
void dfs(当前位置) {
判断当前位置是否处于终点位置
for (向可以移动的位置进行枚举判断) {
int 移动到的新位置;
if (满足可以移动的位置) {
标记新位置已经访问过
dfs(新位置);
可能需要取消标记 // 回溯
}
}
}二、知识精讲 => 连通块
-
连通块定义 连通块是指在网格中，所有满足 “可直接或间接相连” 条件的元素组成的集合。比如消消乐中，同一种动物的相邻（上下左右）元素就构成一个连通块。
-
核心算法逻辑（伪代码拆解）
- 方向数组：
dx[]和dy[]是用来控制移动方向的数组，上下左右四个方向可以表示为：int dx[] = {-1, 1, 0, 0}; // 上、下、左、右 int dy[] = {0, 0, -1, 1}; - DFS 过程：
- 标记当前位置为已访问（避免重复统计）。
- 遍历四个方向，检查新位置是否在网格内、未被访问且属于同一连通块。
- 对符合条件的新位置递归调用 DFS，继续探索。
- 方向数组：
-
典型应用场景
- 消消乐类游戏中，统计可消除的同色元素数量。
- 图论中的岛屿数量问题、洪水填充问题。
- 迷宫 / 地图中的区域划分问题。
三、例题一 数水坑（八联通 连通块）
题目描述
由于近期的降雨，雨水汇集在田地不同的地方。用一个 N×M(1≤N≤100,1≤M≤100) 的网格图表示，每个网格有水W或是旱地.。一个网格与其周围八个网格相连，一组相连的水网格视为一个水坑。求田地中一共有多少个水坑。
输入格式
第一行两个整数 N,M。接下来 N 行，每行 M 个无空格字符，仅包含W和.。
输出格式
输出水坑总数量。
样例输入
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
样例输出
3题目解析
这是一道经典的八连通连通块统计问题，核心就是用DFS（深度优先搜索） 找到所有相连的W（水坑），统计总共有多少组独立的水坑。
一、先看懂题目
- 地图是
N×M的网格，W= 水，.= 旱地 - 8 连通：一个水坑能和上下左右、左上、左下、右上、右下 8 个方向的水相连
- 目标：统计独立水坑的总数
二、完整代码 + 逐模块解析
#include <bits/stdc++.h> // 万能头文件，包含所有C++常用库
using namespace std;
// 全局变量：地图大小n行m列，ans统计水坑数量，mp存储地图
int n, m, ans=0;
char mp[101][101]; // 地图数组，最大100x100，开101方便从1开始计数
// 八联通方向数组：对应 上、下、左、右、左上、左下、右上、右下
int dx[]={0, -1, 1, 0, 0, -1, 1, -1, 1};
int dy[]={0, 0, 0, -1, 1, -1, -1, 1, 1};
// DFS函数：把(x,y)所在的整个水坑全部变成.（标记为已访问）
void dfs(int x, int y) {
mp[x][y] = '.'; // 核心：访问过的水坑，直接改成旱地，避免重复统计
// 遍历8个方向（i从1到8，对应8个联通方向）
for(int i=1;i<=8;i++) {
int nx = x + dx[i]; // 新位置的行号
int ny = y + dy[i]; // 新位置的列号
// 判断条件：
// 1. 新坐标不越界 2. 新位置是水(W)
if(nx>0 && ny>0 && nx<=n && ny<=m && mp[nx][ny] == 'W')
dfs(nx, ny); // 递归继续搜索
}
return;
}
int main() {
// 1. 输入地图尺寸 N行 M列
cin >> n >> m;
// 2. 输入地图（从1,1开始存，不用处理0行0列，越界判断更简单）
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> mp[i][j];
// 3. 遍历整个地图，寻找水坑
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
// 找到一个未被访问的水坑(W)
if(mp[i][j] == 'W') {
dfs(i, j); // DFS把整个水坑标记为.
ans++; // 找到一个独立水坑，计数+1
}
// 4. 输出答案
cout << ans << endl;
return 0;
}
三、核心重点拆解（最关键！）
1. 八连通方向数组
int dx[]={0, -1, 1, 0, 0, -1, 1, -1, 1};
int dy[]={0, 0, 0, -1, 1, -1, -1, 1, 1};
dx：行的变化（上下）dy：列的变化（左右）i=1~8刚好对应8 个方向，覆盖所有相邻格子
2. DFS 的核心作用
dfs(x,y) 做一件事：把坐标 (x,y) 所在的整个连通水坑 **，全部变成 .**
- 相当于给这个水坑打标记：我已经统计过了
- 后续遍历就不会重复计算这个水坑
3. 主函数逻辑（最容易理解）
- 读入地图
- 逐行逐列扫描
- 遇到
W→ 说明找到新水坑 - 调用 DFS 把整个水坑消掉 → 答案 + 1
- 最后输出总答案
四、运行流程（样例演示）
以样例输入为例：
- 扫描到第一个
W - DFS 把这一整块连通的
W全变成. - 答案 +1
- 继续扫描，遇到下一个没被消掉的 W
- 重复操作，直到扫描完整个地图
- 最终统计出 3 个独立水坑，输出 3
五、代码优化点（为什么这么写）
- 数组从 1 开始存：不用判断
nx>=0，越界判断更简单 - 直接修改地图：不用额外开标记数组，节省空间、代码更简洁
- 8 方向循环：完美匹配题目要求
六、总结
这道题就是连通块模板题，记住这套逻辑：
- 定义方向数组
- 写 DFS：标记当前点 + 遍历所有方向 + 递归合法点
- 遍历地图，遇到未标记的起点就 DFS + 计数
三、例题二 填充颜色（反向DFS）
题目描述
由数字 0 组成的方阵中，存在由数字 1 构成的闭合圈，围墙仅上下左右四方向连通。要求将闭合圈内部所有 0 改成 2，圈外 0 保持不变，数字 1 保持不变。
输入格式
第一行一个整数 n(1≤n≤30)。接下来 n 行，每行 n 个整数，构成 n×n 的 01 方阵。
输出格式
输出修改完成后的完整方阵，数字间空格隔开。
样例输入
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 1 1
1 1 1 1 1 0
样例输出
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 1 1
1 1 1 1 1 0 题目解析
这道题是经典的反向 DFS Flood Fill（洪水填充） 题目，核心思路：从边界外开始填充，标记所有外部的 0，剩下没被标记的内部 0 就是要填 2 的区域。
一、先看懂题目
- 方阵里有 0（空白） 和 1（围墙）
- 1 围成闭合圈
- 要求：圈内部的 0 → 改成 2，圈外部的 0 保持不变，1 保持不变
二、核心思路（最重要！）
正向思路（难）：找圈里的 0
反向思路（简单，代码用的这个）：
- 从方阵最最外面的 (0,0) 开始 DFS
- 把所有能连通到外部的 0全部标记为「已访问」
- 最后遍历方阵：
- 是 1 → 原样输出
- 是 0 + 没被访问 → 圈内部 → 输出 2
- 是 0 + 被访问 → 圈外部 → 输出 0
三、完整代码 + 逐行解析
#include <bits/stdc++.h> // 万能头文件
using namespace std;
int n, mp[32][32]; // n是方阵大小，mp存地图
bool vis[32][32]; // 标记是否访问过（标记外部的0）
// 四联通：上下左右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// DFS：从外部往内部填充，标记所有外部0
void dfs(int x, int y) {
// 递归终止条件（4个满足任意一个就返回）
// 1. 越界 2. 已经访问过 3. 遇到墙（1）
if (x < 0 || x > n + 1 || y < 0 || y > n + 1 || vis[x][y] || mp[x][y] == 1)
return;
vis[x][y] = true; // 标记当前位置：这是外部的0
// 遍历4个方向，继续填充
for (int i = 0; i < 4; i++)
dfs(x + dx[i], y + dy[i]);
}
int main() {
cin >> n;
// 输入n*n方阵（从1~n存，方便外围留空间）
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> mp[i][j];
// 关键！从 (0,0) 开始DFS，标记所有外部0
dfs(0, 0);
// 输出最终方阵
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
// 如果是0 且 没被访问 → 内部0 → 输出2
if (mp[i][j] == 0 && !vis[i][j])
cout << 2 << " ";
// 否则原样输出（1 或 外部0）
else
cout << mp[i][j] << " ";
}
cout << endl; // 每行结束换行
}
return 0;
}
四、重点模块逐句拆解
1. 方向数组（四联通）
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
对应：
- 上：x-1, y
- 下：x+1, y
- 左：x, y-1
- 右：x, y+1题目只允许上下左右走，所以用 4 个方向。
2. DFS 函数（核心）
void dfs(int x, int y) {
if (x < 0 || x > n + 1 || y < 0 || y > n + 1 || vis[x][y] || mp[x][y] == 1)
return;
vis[x][y] = true;
for (int i = 0; i < 4; i++)
dfs(x + dx[i], y + dy[i]);
}
作用：把所有外部连通的 0全部标记为已访问。
终止条件解释：
x < 0 || x > n+1：超出整个地图范围，停止vis[x][y]：已经访问过，停止mp[x][y]==1：遇到围墙，无法穿过，停止
3. 关键一步：从 (0,0) 开始搜索
dfs(0, 0);
- (0,0) 不在方阵内部，是最外围
- 从这里 DFS，能把所有和外部连通的 0全部标记
- 1 是墙，DFS 穿不过去 → 内部 0 不会被标记
4. 输出判断逻辑
if (mp[i][j] == 0 && !vis[i][j])
cout << 2 << " ";
else
cout << mp[i][j] << " ";
- 0 + 没被访问 → 圈内部 → 填 2
- 0 + 被访问 → 圈外部 → 保持 0
- 1 → 围墙 → 保持 1
五、运行流程（样例演示）
- 输入 6×6 地图
- 从 (0,0) 开始 DFS
- 标记所有外部 0
- 遍历地图：
- 没被标记的 0 → 输出 2
- 其他 → 原样输出
- 得到正确答案
六、为什么这道题要用「反向 DFS」？
- 正向找闭合圈内部很难
- 反向从外部填充，把外部 0 标记，剩下的自然就是内部
- 代码简单、效率高、不易错
- 这是算法竞赛最常用的套路
七、总结（背会这套模板）
- 反向 DFS：从边界外开始搜索
- 标记外部 0，内部 0 不标记
- 输出：未标记的 0 → 2
- 属于 Flood Fill 洪水填充 经典题型
四、例题三 细胞（正向 DFS Flood Fill）
题目描述
一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞。细胞的定义为：沿细胞数字上下左右还是细胞数字，则为同一细胞。求给定矩形阵列的细胞个数。
输入格式
第一行为矩阵的行数 n 和列数 m(1≤n,m≤1000)。下面为一个 n×m 的矩形阵列。
输出格式
一个整数，表示细胞的个数。
样例输入
4 10
0234500067
1034560500
2045600671
0000000089
样例输出
4
题目解析
这道题是经典的正向 DFS Flood Fill（洪水填充） 题目，核心思路：遍历地图，每找到一个未被访问的细胞（1-9），就用 DFS 把整片连通的细胞全部标记消除，同时计数加一。
一、题意理解
- 方阵元素：
0（无细胞）、1-9（细胞） - 规则：上下左右四联通，相连的细胞视为同一个
- 要求：统计总共有多少个独立的细胞块
二、核心思路（最重要！）
- 遍历扫描：逐行逐列扫描整个地图
- 发现起点：如果遇到非 0 数字（细胞）
- DFS 消除：调用 DFS，把这一整片连通的细胞都变成 0
- 计数 + 1：每消除一整片，就代表找到一个细胞
- 最终输出：总计数就是答案
三、完整代码 + 逐行解析
#include <bits/stdc++.h> // 万能头文件
using namespace std;
int n, m, ans=0; // n行m列，ans统计细胞个数
int mp[1001][1001]; // 地图数组，数据范围1000x1000
// 四联通：上 下 左 右
int dx[]={0, -1, 1, 0, 0};
int dy[]={0, 0, 0, -1, 1};
// DFS函数：把(x,y)所在的整片细胞变成0（消除标记）
void dfs(int x, int y) {
mp[x][y] = 0; // 核心：把当前细胞变成0，标记为已访问
// 遍历4个方向（i=1到4）
for(int i=1;i<=4;i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 判断：不越界 + 不是0（是细胞）
if(nx>0 && ny>0 && nx<=n && ny<=m && mp[nx][ny] != 0)
dfs(nx, ny); // 递归搜索
}
return;
}
int main() {
cin >> n >> m;
// 输入地图：按字符串读取，转成数字存入数组
for(int i=1;i<=n;i++) {
string tmp;
cin >> tmp;
for(int j=0;j<m;j++) {
mp[i][j+1] = tmp[j] - '0';
}
}
// 遍历地图找细胞
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
// 找到一个未被访问的细胞
if(mp[i][j] != 0) {
dfs(i, j); // 消除整片细胞
ans++; // 计数+1
}
// 输出答案
cout << ans << endl;
return 0;
}
四、重点模块拆解
1. 方向数组（四联通）
int dx[]={0, -1, 1, 0, 0};
int dy[]={0, 0, 0, -1, 1};
- 对应移动：上、下、左、右
- 题目要求四联通，所以只遍历
i=1~4
2. DFS 核心函数
作用：消除一整片连通的细胞
- 把当前位置变成
0，防止重复搜索 - 向四个方向扩散，遇到非 0 数字就继续递归
3. 字符串输入处理
string tmp; cin >> tmp;
mp[i][j+1] = tmp[j] - '0';
- 输入是连续数字串（如
0234500067），不能直接读整数 - 用
string读取，再转成数字存入地图 tmp[j] - '0'：字符转数字（'0'→0，'1'→1...）
4. 主函数逻辑
- 读入地图
- 双重循环扫描
- 遇到非 0 数字 → DFS 消除整片 → 答案 + 1
- 输出总细胞数
五、运行流程（样例演示）
- 输入 4×10 地图
- 扫描到第一个非 0 数字
2 - DFS 把整片连通细胞变 0 → 答案 = 1
- 继续扫描，遇到下一个非 0 数字
1 - DFS 消除 → 答案 = 2
- 重复直到扫描结束
- 最终答案 = 4
六、易错点提醒
- 方向数量错误：题目是四联通，不能写成 8
- 输入处理：必须用字符串读取连续数字
- 数组大小：数据范围 1000，数组要开到
1001
七、核心总结（必背模板）
- 解题思想：正向 DFS + 洪水填充
- 核心操作：找到非 0 起点 → DFS 消除整片 → 计数 + 1
- 联通方式：上下左右四联通
- 题型归类：连通块统计标准模板题
- 适用场景：数水坑、细胞、岛屿、连通块数量
更多推荐
14
0- 0
已为社区贡献1条内容
所有评论(0)