遍历每一个元素，在数组意义上叫做暴力枚举，在图上就是搜索，按遍历顺序有深度优先搜索（DFS）和广度优先搜索（BFS）两种方式。
二叉树的遍历就是典型的 DFS。
// 中序遍历void inorder(TreeNode* root) {if (!root) {return;}// ...inorder(root->left, res);inorder(root->right, res);}
同样是图，可以把在树上走改为在方格图上走。
例题 1：百练 4103. 踩方格
时间限制: 1000ms 内存限制: 65536kB 描述
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走步，共有多少种不同的方案。
种走法只要有一步不一样，即被认为是 不同的方案。 输入
允许在方格上行走的步数#card=math&code=n%20%28n%20%3C%3D%2020%29&id=esfpw) 输出
计算出的方案数量 样例输入 2 样例输出 7
在此题中，我们要遍历的是每一种可能的走法，都是一种路径。对于每一步，你可以有多种选择（向北走、向东走、向西走），也就是说，我们要遍历每一步的每一种选择，找到所有的方案。
此外，并不是每一步的每种选择都可行，且总步数不能超过 ，我们有一些终止条件。
参考代码 1
#include <iostream>#include <algorithm>using namespace std;bool vis[24][44];int ways(int i, int j, int n) {if (vis[i][j]) { // 回溯：不能访问当前格return 0;}if (n == 0) { // 终止：步数耗尽return 1;}vis[i][j] = true; // 标记当前格为已访问int ans = 0;// 尝试三种走法ans += ways(i + 1, j, n - 1);ans += ways(i, j + 1, n - 1);ans += ways(i, j - 1, n - 1);vis[i][j] = false; // 恢复现场：未访问return ans;}int main() {int n;cin >> n;int x = 0, y = 22;cout << ways(x, y, n) << endl;return 0;}
它的思路是：
在上面的代码，我们使用了 bool vis[][] 来标记格点是否已访问（题目要求不能同一路线重复访问），这是一个常见的技巧。
ways() 函数在尝试三种走法时，调用了自身，使代码简洁易懂，这一用法是「递归」。这么做的逻辑在于，走下一步的逻辑和这一步完全一致，只改变 ways() 接收的参数即可，这是 dfs 的特征之一。使用递归时，必须有终止条件结束无限的调用，否则程序将会运行超时或内存超限。
在程序的某一层，一次递归结束后，程序从递归调用处，继续执行下文。这一次递归很可能找不到合适的解，而遇到了拒绝条件，我们把这一现象叫做「回溯」，这是 dfs 的特征之二。它形象地描述了程序尝试所有可能选择的过程。
有时在回溯过后，我们需要「恢复现场」，以便进行后续计算。这一点要根据题目的具体情况分析。
事实上，从另一种角度理解，我们 dfs 的对象可以是试图寻路的决策树，递归的过程类似于树的遍历的递归写法，回溯的操作可以看做剪枝。
这种理解方式是一种抽象，把在图上的行走抽象为每一步的三种决策，实际代码、做法没有改变。事实上，dfs 经常可以解决这种抽象的决策问题，而不局限于图。从不同的理解角度，这类方法也被叫做递归方法、回溯法，它们的实质仍然是 dfs。
例题 2：AcWing 3472. 八皇后
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。 如何将 8 个皇后放在棋盘上（有 8×8 个方格），使它们谁也不能被吃掉！ 这就是著名的八皇后问题。 对于某个满足要求的 8 皇后的摆放方法，定义一个皇后串 a 与之对应，即
，其中
为相应摆法中第 i 行皇后所处的列数。 已经知道 8 皇后问题一共有 92 组解（即 92 个不同的皇后串）。 给出一个数 b，要求输出第 b 个串。 串的比较是这样的：皇后串 x 置于皇后串 y 之前，当且仅当将 x 视为整数时比 y 小。
输入格式
第一行包含整数 n，表示共有 n 组测试数据。 每组测试数据占 1 行，包括一个正整数 b。
输出格式
输出有 n 行，每行输出对应一个输入。 输出应是一个正整数，是对应于 bb 的皇后串。
数据范围
输入样例：
输出样例：
15863724 84136275
参考代码 2
#include <iostream>#include <cmath>#include <vector>#include <algorithm>using namespace std;const int N = 8;char b[N + 4];vector<string> ans;bool check(int n) { // 判断已经放置的 n + 1 个皇后是否合理for (int i=0; i<n; ++i) {if (b[i] == b[n] || abs(n - i) == abs(b[n] - b[i])) //dx == dyreturn false;}return true;}void dfs(int n) { // 尝试放置第 [0, N) 行的皇后if (n == N) { // 终止：放置完毕，记录答案string t;for (int i=0; i<N; ++i) {t += to_string(b[i] + 1);}ans.push_back(t);return;}for (int i=0; i<N; ++i) { // 尝试在 a[n][i] 位置放置b[n] = i; // 放置if (check(n)) { // 可以放置dfs(n + 1); // 尝试放置下一个}// b[n] = 0; 这里不需要还原现场的原因是，回溯后它的取值不会被用到，不影响}}int main() {dfs(0);sort(ans.begin(), ans.end());int t;cin >> t;while (t--) {int i;cin >> i;cout << ans[i - 1] << endl;}return 0;}
在此题中，dfs 就是抽象意义的。不可以放置时，不进行下一层递归，也体现出回溯。
dfs 功能强大，结果可靠，因为它在本质上是一种暴力算法，遍历了每一种可能性。也因此，题目经常限制朴素 dfs ，使其不能在规定时间内完成搜索。这时候可以使用通过剪枝减少不必要的搜索，来优化运行速度。对于考察 dfs 的题目来说，好的剪枝能极大提升运行速度，是通过题目不可或缺的部分。下文将演示剪枝的过程。
例题 3：百练 1724. Roads
- 时间限制： 1000ms 内存限制： 65536KB
- 描述
N 个以数字 1 … N 命名的城市与单向道路相连。每条道路都有两个与之相关的参数：道路长度和需要为道路支付的通行费（以硬币数量表示）。 鲍勃和爱丽丝以前住在城市 1。鲍勃发现爱丽丝在他们喜欢玩的纸牌游戏中作弊后，与她分手并决定搬走——到城市 N。他想尽快到达那里有可能，但他缺现金。
我们想帮助 Bob 找到从城市 1 到城市 N的最短路径，这是他用他拥有的钱所能负担的。- 输入
输入的第一行包含整数 K，0 <= K <= 10000，Bob 可以在途中花费的最大硬币数。
第二行包含整数 N，2 <= N <= 100，城市总数。
第三行包含整数 R，1 <= R <= 10000，道路总数。 以下每一行通过指定由单个空白字符分隔的整数 S、D、L 和 T 来描述一条道路：
S 是源城市，1 <= S <= N
D 是目的地城市，1 <= D <= N
L 是道路长度，1 <= L <= 100
T 为通行费（以硬币数量表示），0 <= T <=100
请注意，不同的道路可能具有相同的源城市和目标城市。- 输出
输出的第一行也是唯一一行应该包含从城市 1 到城市 N 的最短路径的总长度，其总通行费小于或等于 K 个硬币。 如果这样的路径不存在，则只应将数字 -1 写入输出。- 样例输入
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
- 样例输出
11
我们根据所学的基础 dfs 知识，可以写出如下代码，使得样例可以通过。
参考代码 3-1
#include <bits/stdc++.h>using namespace std;const int N = 100 + 4;const int inf = 0x3f3f3f3f;struct Edge {int y;int w; // lengthint c; // cost} e;vector<Edge> g[N];bool vis[N];int n, k, m;int ans = inf;// @len统计当前路程 @cost当前花费void dfs(int s, int len, int cost) {if (s == n) { // 终止：到达目的地，更新答案ans = min(ans, len);return;}if (vis[s]) { // 回溯：节点已访问return;}vis[s] = true;for (int i=0; i<g[s].size(); ++i) {e = g[s][i];if (cost + e.c <= k) { // 回溯：通行费不足dfs(e.y, len + e.w, cost + e.c);}}vis[s] = false; // 恢复现场}int main() {// readcin >> k >> n >> m;for (int i=0; i<m; ++i) {int s;cin >> s >> e.y >> e.w >> e.c;g[s].push_back(e);}// dfsdfs(1, 0, 0);if (ans == inf) {cout << -1 << endl;} else {cout << ans << endl;}return 0;}
代码中，0x3f3f3f3f是一个大整数，常用于表示无穷大。它的好处是是 inf * 2 不会溢出
阅读：【算法设计与数据结构】为何程序员喜欢将INF设置为0x3f3f3f3f？
它的总体思路是遍历所有可能的走法，每找到一条路，就尝试更新答案。当我们搜索过所有路，答案就被更新为可能的解中的最小值。以上的代码能够正确地执行，但我可以透露的是，这份提交的结果是运行超时。
检查我们的 dfs() 函数，除了最基础的终止条件、for 循环遍历邻接表搜索，我们使用了「例题 1 百练 4103. 踩方格」中的 vis[] 数组。此题并没有要求不能重复访问节点，但是显然，一条最短路径不应包括重复的点（除非有负权边），否则它一定不是最优解。我们就没有必要再去搜索它了。这一种思想，就是「剪枝」。剪枝一般可以分为两类：
- 可行性剪枝——继续搜索不可能发现可行解，例如此题中的通行费不足
- 最优性剪枝——继续搜索不可能发现最优解，例如此题中的节点已访问
我们进行剪枝时，放弃继续搜索表现为回溯。你也可以认为回溯也是一种剪枝。在此题中，我们需要进行进一步目的性更强的剪枝，使程序不会超时。
我们首先在 dfs() 加入一条比较常规的剪枝：
if (len >= ans) { // 最优性剪枝：路径长度超过最短纪录
return;
}
注意不可写成 len > ans（缺少相等），二者效率天差地别。这一句话在多数程序中能带来时间效率的一次飞跃。然而很遗憾的是，再次提交，程序仍然超时。
此时我们不得不使出杀手锏——「空间换时间」。我们此题中的空间还有很大开发空间，这也是最优性剪枝的一个常见方法：记录中间结果。
用 midL[k][m] 表示：走到城市 时总过路费为
的条件下，最优路径的长度。若在后续的搜索中，再次走到
时，如果总路费恰好为
，且此时的路径长度已经超过
midL[k][m]，则不必再走下去了。注意这个数组在使用前需要初始化。
参考代码 3-2
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 4;
const int inf = 0x3f3f3f3f;
struct Edge {
int y;
int w; // length
int c; // cost
} e;
vector<Edge> g[N];
int midL[N][10004];
bool vis[N];
int n, k, m;
int ans = inf;
void dfs(int s, int len, int cost) {
if (s == n) { // 终止：到达目的地，更新答案
ans = min(ans, len);
return;
}
if (len >= ans) { // 最优性剪枝：路径长度超过最短纪录
return;
}
if (midL[s][cost] <= len) { // 最优性剪枝：已搜索过更优路径
return;
}
midL[s][cost] = len; // 记录中间结果
if (vis[s]) { // 回溯：节点已访问
return;
}
vis[s] = true;
for (int i=0; i<g[s].size(); ++i) {
e = g[s][i];
if (cost + e.c <= k) { // 回溯：通行费不足
dfs(e.y, len + e.w, cost + e.c);
}
}
vis[s] = false; // 恢复现场
}
int main() {
// read
cin >> k >> n >> m;
for (int i=0; i<m; ++i) {
int s;
cin >> s >> e.y >> e.w >> e.c;
g[s].push_back(e);
}
// init
for (int i=1; i<=n; ++i) {
for (int j=0; j<10004; ++j) {
midL[i][j] = inf;
}
}
// dfs
dfs(1, 0, 0);
// print
if (ans == inf) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}
通过这一系列的操作，最后换来 AC 代码，也是成就感满满的一件事，相信你能从中有所收获。dfs 把问题看成一个又一个的选择，通过暴力搜索，可以解决很多问题，功能十分强大。只是很多时候其时间复杂度也会膨大到难以接受。在后续「动态规划」的章节中，我们会改变「决策」的眼光，用「状态」的眼光重新审视 dfs，那时候你会对这一搜索算法有新的理解。
若有收获，就点个赞吧
0 人点赞
