帅树粉丝团打卡处 - 深度优先搜索
2026-08-09 21:28:48
发布于：广东
104阅读
0回复
0点赞
迷宫1：
伪代码系列：
函数 DFS(当前行 x, 当前列 y):
// 1. 递归出口：判断是否到达终点
如果 (x == 终点行 n 且 y == 终点列 m) 则:
设置全局标志 flag = true (表示找到路径)
直接返回 (return)
// 2. 状态转移：尝试向四个方向移动
遍历 方向数组 dir 中的每一个方向 (共4个):
计算下一个位置的坐标:
nx = x + 当前方向的行偏移量
ny = y + 当前方向的列偏移量
// 3. 剪枝与合法性判断（必须同时满足以下三个条件）
如果 (nx, ny 在地图合法范围内)
且 (nx, ny 尚未被访问过)
且 (地图(nx, ny) 不是墙壁 '#') 则:
// 4. 做选择：标记新位置为已访问
标记 vis[nx][ny] = true
// 5. 递归：从新位置继续向深处搜索
调用 DFS(nx, ny)
// 【注意】：此处没有执行 vis[nx][ny] = false (回溯)
// 原因：本题只求“是否存在路径”，如果走过 (nx, ny) 发现无法到达终点，
// 那么其他路径再走到 (nx, ny) 同样也无法到达终点。
// 因此不需要撤销标记，这能大幅减少重复搜索，提高算法效率。
#include<bits/stdc++.h>
using namespace std;
int n, m; // n:地图行数, m:地图列数
char MAP[49][49]; // 存储地图字符 ('.'表示路, '#'表示墙)
// 方向数组：定义四个移动方向 (右, 下, 左, 上)
// dir[0]: {0, 1} -> 列+1 (向右)
// dir[1]: {1, 0} -> 行+1 (向下)
// dir[2]: {0,-1} -> 列-1 (向左)
// dir[3]: {-1,0} -> 行-1 (向上)
int dir[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
bool vis[49][49]; // 访问标记数组：vis[x][y]=true 表示该点在当前搜索路径中已走过
bool flag = false; // 全局标志位：true表示找到了从起点到终点的路，false表示没找到
// 【辅助函数】检查坐标 (x, y) 是否在地图合法范围内 (1~n, 1~m)
bool inmap(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
/**
* 深度优先搜索函数
* @param x 当前所在的行坐标
* @param y 当前所在的列坐标
*/
void dfs(int x, int y){
// 【递归出口】：如果当前坐标到达了右下角终点 (n, m)
if(x == n && y == m) {
flag = true; // 标记为“已找到路径”
return; // 立即结束当前递归，不再继续搜索
}
// 【尝试移动】：遍历四个方向
for(int i = 0; i < 4; i++){
int nx = x + dir[i][0]; // 计算下一个位置的行坐标
int ny = y + dir[i][1]; // 计算下一个位置的列坐标
// 【合法性判断】必须同时满足三个条件才能走
// 1. inmap(nx,ny): 新位置不能越界
// 2. !vis[nx][ny]: 新位置没有被访问过（防止死循环/走回头路）
// 3. MAP[nx][ny] != '#': 新位置不是障碍物（是空地）
if(inmap(nx, ny) && vis[nx][ny]==0 && MAP[nx][ny] != '#'){
vis[nx][ny] = true; // 【做选择】：标记新位置为“已访问”
dfs(nx, ny); // 【递归】：从新位置继续向深处搜索
// 注意：这里没有 vis[nx][ny] = false (回溯)
// 原因：本题只问“能不能到”，只要走过这个点发现不通，
// 以后也没必要再走它了，所以不需要撤销标记。
}
}
}
int main(){
// 输入地图大小
cin >> n >> m;
// 输入地图数据
// cin >> MAP[i]+1 表示从数组下标1开始存储字符串，方便对应坐标(1,1)
for(int i = 1; i <= n; i++){
cin >> MAP[i]+1;
}
// 【初始化】：标记起点 (1,1) 为已访问，防止重复走起点
vis[1][1] = true;
// 从起点 (1,1) 开始搜索
dfs(1, 1);
// 根据全局标志位输出结果
if(flag) cout << "YES"; // 找到了路径
else cout << "NO"; // 所有路都走完了也没到终点
return 0;
}
迷宫最短路径
伪代码系列：
函数 inmap(坐标 x, 坐标 y):
如果 x 大于等于 1 并且 x 小于等于 地图总行数 n，
并且 y 大于等于 1 并且 y 小于等于 地图总列数 m:
返回 真 (true)
否则:
返回 假 (false)
函数 dfs(当前行 x, 当前列 y, 当前步数 step):
// 【递归出口】：判断是否到达终点
如果 当前坐标 (x, y) 等于 终点坐标 (n, m):
更新全局最短步数 ans = min(ans, step)
结束当前函数调用 (return)
// 【状态扩展】：尝试向四个方向移动
循环 i 从 0 到 3:
计算下一步坐标 nx = x + 方向偏移量[i][0]
计算下一步坐标 ny = y + 方向偏移量[i][1]
// 【合法性与剪枝判断】
如果 下一步在地图内 (inmap(nx, ny))
并且 下一步未被访问过 (!vis[nx][ny])
并且 下一步不是墙壁 (MAP[nx][ny] != '#'):
// 1. 标记状态：将下一步标记为已访问
vis[nx][ny] = true
// 2. 递归深入：带着新坐标和步数+1继续搜索
dfs(nx, ny, step + 1)
// 3. 回溯状态：取消标记，恢复为未访问，以便其他路径可以经过此点
vis[nx][ny] = false
#include<bits/stdc++.h>
using namespace std;
int n, m; // n:地图行数, m:地图列数
char MAP[20][20]; // 存储地图数据 ('.'表示路, '#'表示墙)
// 方向数组：分别代表 右、下、左、上 四个方向的坐标偏移量
// dir[0]: (0, 1) -> 向右
// dir[1]: (1, 0) -> 向下
// dir[2]: (0, -1)-> 向左
// dir[3]: (-1, 0)-> 向上
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool vis[20][20]; // 访问标记数组：vis[x][y]=true 表示该点当前路径中已走过，防止走回头路
int ans = 100; // 记录最短步数。初始化为一个较大的值（题目限制最多100步），作为“无穷大”的替代
// 【辅助函数】判断坐标 (x, y) 是否在地图范围内
bool inmap(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
/**
* DFS 深度优先搜索函数
* @param x 当前所在的行坐标
* @param y 当前所在的列坐标
* @param step 从起点走到当前位置已经消耗的步数
*/
void dfs(int x, int y, int step) {
// 【递归出口】：如果当前坐标等于终点坐标 (n, m)
if (x == n && y == m) {
// 更新全局最优解：取“当前已知最短”和“本次走的步数”中的较小值
ans = min(ans, step);
return; // 找到一条路后返回，去尝试其他路径
}
// 【尝试四个方向】：按照 右->下->左->上 的顺序尝试移动
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0]; // 计算下一步的行坐标
int ny = y + dir[i][1]; // 计算下一步的列坐标
// 【剪枝与合法性判断】必须同时满足三个条件才能走：
// 1. inmap(nx, ny): 下一步不能走出地图边界
// 2. !vis[nx][ny]: 下一步必须是没走过的（避免死循环）
// 3. MAP[nx][ny] != '#': 下一步不能是障碍物（墙壁）
if (inmap(nx, ny) && !vis[nx][ny] && MAP[nx][ny] != '#') {
vis[nx][ny] = true; // 【标记】：把下一步标记为“已访问”，防止后续重复走
dfs(nx, ny, step + 1); // 【递归】：带着新的坐标和步数+1，继续深入搜索
vis[nx][ny] = false; // 【回溯】：关键点！
// 当从 deeper 层返回时，说明这条路走完了（或者是死胡同）。
// 必须把标记取消，恢复为“未访问”，以便其他路径可以再次经过这个点。
}
}
}
int main() {
// 1. 输入地图大小
cin >> n >> m;
// 2. 输入地图内容
// cin >> MAP[i]+1 是一种技巧，让字符串从下标1开始存储，方便与坐标(1,1)对应
for (int i = 1; i <= n; i++) {
cin >> MAP[i] + 1;
}
// 3. 初始化起点
vis[1][1] = true; // 标记起点已访问
dfs(1, 1, 0); // 从 (1,1) 出发，初始步数为 0
// 4. 输出结果
// 如果 ans 还是初始值 100，说明 DFS 跑完了都没找到终点，即无法到达
if (ans == 100)
cout << -1;
else
cout << ans;
return 0;
}
全排列
#include<bits/stdc++.h>
using namespace std;
int n; // 全局变量：表示要排列的数字总个数 (1~n)
bool vis[11]; // 标记数组：vis[i] = true 表示数字 i "已经被用过了"，false 表示"还没用"
int p[11]; // 结果数组：p[idx] 表示第 idx 个位置上填的是哪个数字
// dfs函数：专门负责去填第 idx 个位置
void dfs(int idx){
// 【递归出口】：如果 idx 变成了 n+1，说明前 n 个位置都已经填好了数字
if(idx == n + 1){
// 此时 p[1] 到 p[n] 里存的就是一种完整的排列方案，直接打印出来
for(int i = 1; i <= n; i++){
cout << p[i] << " ";
}
cout << endl; // 打印完一种方案后换行
return ; // 结束当前这层递归，回到上一层去尝试别的可能
}
// 【尝试填数】：我们要给第 idx 个位置填数字，从 1 到 n 挨个尝试
for(int i = 1; i <= n; i++){
// 【剪枝判断】：看看数字 i 是不是已经被前面的位置用掉了？
// 如果 vis[i] 是 false，说明数字 i 目前空闲，可以填！
if(vis[i] == false) {
// --- 1. 做选择 (进入下一层递归前) ---
p[idx] = i; // 动作A：把数字 i 填入第 idx 个坑位
vis[i] = true; // 动作B：把数字 i 标记为"已占用" (注意这里下标必须是 i)
// --- 2. 递归 (深入下一层) ---
dfs(idx + 1); // 第 idx 个位置搞定了，现在去处理第 idx+1 个位置
// --- 3. 撤销选择 (回溯) ---
// 当上面的 dfs 跑完回来，说明以当前状态往下走的所有情况都试完了。
// 我们需要把现场清理干净，让数字 i 恢复空闲，以便在其他分支中被使用。
vis[i] = false; // 动作C：把数字 i 的占用标记取消 (回溯的核心)
p[idx] = 0; // 动作D：清空这个坑位 (其实这句不写也没事，因为下次循环会被覆盖，但写上逻辑更严谨)
}
}
}
int main(){
cin >> n; // 输入 n，比如输入 3
dfs(1); // 从第 1 个位置开始填数
return 0;
}
图的遍历
#include <bits/stdc++.h> // 包含所有标准库，方便竞赛使用
using namespace std;
// 定义全局变量
// mp 是邻接表，mp[x] 存储与 x 相连的所有朋友的编号
vector<int> mp[100005];
// vis 是标记数组，vis[x] = true 表示 x 已经被访问过（已经属于某个圈子了）
bool vis[100005];
int n, m; // n: 人数, m: 关系对数
/**
* DFS 深度优先搜索函数
* 作用：从 x 出发，把所有和 x 直接或间接相连的人全部标记为“已访问”
*/
void dfs(int x) {
// 遍历 x 的所有邻居（朋友）
for (int i = 0; i < mp[x].size(); i++) {
int next = mp[x][i]; // 取出第 i 个朋友 next
// 如果这个朋友还没被访问过
if (!vis[next]) {
vis[next] = 1; // 标记为已访问
dfs(next); // 递归：继续去访问 next 的朋友
}
}
}
int main() {
// 1. 输入人数 n 和关系数 m
cin >> n >> m;
// 2. 建图：读取 m 对关系
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
// 无向图：u 认识 v，v 也认识 u，所以两边都要存
mp[u].push_back(v);
mp[v].push_back(u);
}
int cnt = 0; // cnt 用来记录朋友圈的总数
// 3. 核心逻辑：枚举每一个人
for (int i = 1; i <= n; i++) {
// 如果第 i 个人还没有被访问过
if (!vis[i]) {
cnt++; // 发现了一个新的朋友圈，计数器 +1
vis[i] = 1; // 先把这个人自己标记上
dfs(i); // 启动 DFS，把他整个圈子里的人都找出来并标记
}
}
// 4. 输出结果
cout << cnt;
return 0;
}
~~
全部评论 3
.--.-. -------...-.--. ----.-.....-.-- -.--..-..-.-.-. -..-.--.-.-----. -..---.-....--. -----.--...-.--.- --------....--.. --...-....-...- -.-...--...--.- -..---..-.----- -..---.....--.- -.--.--.--..--. -..---.-....--. --..........-. / -..-....-.-...-- -..----.--..... -..---...---.-. -.-.-.-.--..-.- -...------.--... -...-..--......- -...------...--- --..---.--..-.-
1周前 来自 广东
0
有帮助，赞一个