#创作计划# DFS深度优先搜索

энтджей

2026-07-27 17:16:01

发布于：浙江

9阅读

0回复

0点赞

前言：

本帖是讲解 $DFS$ 的，阅读前需要会编写A+B problem（被删了，所以你得有会编写A+B）的编程石粒，以语文分数不低于0分的石粒
为了维持ACGO的风度，所以大部分代码为伪代码，防止有神秘人直接复制粘贴。
代码有很多我打比赛保留的一些习惯，可跳过，因为本来就没用
废话不多说直接结束开始

正片

1.了解 $DFS$ ：
- $DFS（Depth-First Search）$ ，英译：深度优先搜索
- 同事： $BFS$ 等
- 核心用处：用于走迷宫，全排列（枚举）、遍历图/树等
- 中心思想：“不撞南墙不回头”，沿着一条路一直走下去，直到无路可走，然后回溯到上一个可以走的地方，重复此操作。
  - 拿迷宫举例（本图选自A7991的样例1）（有点糊，请见谅）
  - 想必你已经看懂了吧，由此可见 $DFS$ 的中心思想，~~比对一下，DFS可以走迷宫，但BFS更适合走迷宫~~
2.尝试实现 $DFS$ ：
- 既然 $DFS$ 是从一个点一直向外走，走到头再回溯，由此可见， $DFS$ 可以用递归实现，~~哪里可见了？~~
- 那么我们来尝试一下下吧：
```
void dfs(入参) {
	if (结束条件) {
		完成更新或输出等
		return ;
	}
	for (尝试枚举/遍历/移动) {
        标记，防止重复选取/遍历
		开始递归：dfs (入参);
        回溯，即取消标记（不一定有哈）
	}
}
```
- 这是一个通用的伪代码，可以用于很多题目，但是如何正确使用呢，请继续往后看

3.完善 $DFS$ ：

因为上面的代码是通用的，那么我们要写出一些适用于特别题目的代码：

(1).迷宫：

void dfs(int 现在位置x, int 现在位置y, int 步数（可有可无看实际情况）) {
	if (结束条件为：现在x等于目标x&现在y等于目标y) {
		完成更新最少步数或输出可以抵达终点等
		return ;
	}
	for (尝试枚举4中走路方式) {
		int 更新后的x, 更新后的y;
		if (越界) continue;
		if (已经访问过) continue;
		if (不可以走) continue;
		将此位置更新为已访问
		递归：dfs (更新后的x, 更新后的y, 步数+1);
		此处不需要回溯（把！
	}
}

(2). 枚举所有排列：

void dfs(string 已经有的数字, int 已经用到第几个数字) {
	if (结束条件为：已经用到最后一个数字) {
		输出这次排列结果
		return ;
	}
	for (尝试枚举后续可以使用的数字) {
		此处不需要标记是否已用过，因为已经有"已经用到第几个数字"这个变量
		递归：dfs (更新后的排列，此次用的数的下标);
		此处不需要回溯！
	}
}

完善了代码，那么我们上实战

4.实战：

T1：A7991.迷宫（没错他又来了）

(1). 分析题目：
- 给定起点、终点、地图，让你求是否可以从起点走到终点。这是一道典型的迷宫，可以使用3.(1)迷宫中的模版代码来写：
(2). 代码思路：
- 按照题目输入后，从起点调用一次 $DFS$ 得到结果。

(3). 代码实现:

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 50;
const int INF = 1e18;

int n, m;
int sx, sy, fx, fy;
char mp[N][N];
bool flag = false;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool vis[N][N];
void dfs (int x, int y) {
    if (结束条件) { 
        更新全局变量flag，表示可以成功
        return ;
    } 
    for (int i = 0; i < 4; i++) {
        int nx = 更新后的x;
        int ny = 更新后的y;
        if (越界) continue;
        if (已访问) continue;
        if (障碍物) continue;
        更新vis[nx][ny]为已访问
        递归调用
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	// freopen("", "r", stdin);
	// freopen("", "r", stdout);

    输入n, m, sx, sy, fx, fy, mp
    调用一次DFS
    dfs (sx, sy);
    cout << (flag == true ? "YES" : "NO");
    return 0;
}

T2：A149.数水坑

(1). 分析题目：
- 这个题目的本质是连通块，这个没有讲过，让我们一起看看。
- 给你 $n$ , $m$ 以及地图，求有多少个水坑，水坑的定义为一个有水的地方的8个方向里有水的话把它们看做一个水坑（当然，如果又多个/1个连着1个，1个连着1个都算做一个）
(2). 代码思路：
- 查找到每一个没有访问过的水，开始深搜，遍历所有与他相连的水，这就是一个水坑，让计数变量自增

(3). 代码实现:

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 110;

int n, m;
char mp[N][N];
int water;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};
void dfs (int x, int y){
    for(int i = 0;i < 8;i++){
    	int nx = 更新后的x;
        int ny = 更新后的y;
        if(越界) continue;
        if(不是水) continue;
        这里有一个小巧思，既然上面判断的是是不是水，那么我们将是水的并且已将访问过的地方改成不是水不就好啦
        递归调用
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	// freopen("", "r", stdin);
	// freopen("", "r", stdout);
	
    输入 n, m, mp
    循环检测每一个节点
            if(如果是水则DFS){
                dfs(i, j);
                计数变量增加
            }
        }
    }
    cout << water;
    return 0;
}

T3：A139.组合的输出

(1). 分析题目：
- 给定可用数字范围，可用数字，让你求所有全排列。这是一道典型的全排列，可以使用3.(2)全排列中的模版代码来写会PE，也可以将 $string$ 替换为 $vector$
(2). 代码思路：
- 直接暴力枚举，利用 $DFS$ 的特性进行全排列

(3). 代码实现:

注意，这题有坑，注意空格在数字前面，否则会PE

#include<bits/stdc++.h>
#define int long long  
using namespace std;
int n, r;
void dfs (string ans, int id, int cnt) {
    if (用了r个数字) {
        输出
        return ;
    }
    if (已经超过n这个范围了) {
        停止dfs
        return ;
    }
    for (枚举) {
        dfs (更新后的ans, 更新最后用的数字并加一, 使用的数字个数加一);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	// freopen("", "r", stdin);
	// freopen("", "r", stdout);
	
	输入
    dfs ("", 1, 0);
    return 0;
}