全排列与 DFS：信息学竞赛中的暴力骗分
在信息学竞赛中，经常会遇到要求安排顺序的题目。例如，给几个任务安排执行顺序，或者决定访问几个地点的先后顺序。
如果暂时想不到高效的算法，可以试试最直接的办法：把所有可能的顺序都枚举出来，一个一个检查。
这种做法叫作暴力枚举。数据较小时，它往往能直接得到正确答案；数据较大时，也可能帮我们拿到部分分数。
这一节学习怎样用递归实现全排列。
一、什么是全排列？
给定三个数字 1、2、3，要求每个数字恰好使用一次，把它们排成一排。
一共有 6 种排法：
这就是全排列。
如果有 n 个不同的数字，那么一共有 n! 种排列。
这里的 ! 表示阶乘：
* 3! = 3 × 2 × 1 = 6
* 4! = 4 × 3 × 2 × 1 = 24
* 5! = 5 × 4 × 3 × 2 × 1 = 120
为什么三个数字有 6 种排法？
因为第一个位置可以选 3 个数字中的任意一个；第二个位置只能从剩下的 2 个数字中选；最后一个位置只剩 1 个数字。
所以总共有 3 × 2 × 1 = 6 种排法。
二、怎样用 DFS 枚举全排列？
我们不需要一次性想好整个排列。
只需要从左到右，每次确定一个位置上的数字。
还是以 1、2、3 为例：
我们先确定第一个位置，再确定第二个位置，一直往下，直到得到一个完整的排列。
找到一个排列后，再返回之前的位置，换一个数字继续尝试。
这就是深度优先搜索，简称 DFS。
在代码中，可以使用递归函数：
其中，k 表示当前正在填写第几个位置。
例如，dfs(2) 的任务，就是确定排列中第 2 个位置的数字，再继续填写后面的数字。
三、全排列的三个关键变量
写代码之前，先准备下面三个变量：
它们的作用分别是：
变量 含义 n 一共有多少个数字 a[k] 第 k 个位置选择了哪个数字 vis[i] 数字 i 是否已经使用
其中，vis[i] = true 表示数字 i 已经使用，不能重复选择。
为什么需要 vis 数组？
因为全排列要求每个数字恰好出现一次。
如果前面已经选过数字 2，后面就不能再选 2。
但是，当我们完成一种排列，准备尝试另一种排列时，之前用过的数字应该允许再次使用。
所以除了记录数字有没有使用，还要学会在递归返回之后取消标记。
这个操作叫作回溯。
四、第一道题：P1706 全排列问题
题目链接：https://www.luogu.com.cn/problem/P1706
题目要求
输入一个整数 n，按照字典序输出 1 到 n 的所有全排列。
数据范围：1 ≤ n ≤ 9。
这是一道标准的 DFS 全排列模板题。
参考代码
代码讲解
先看递归结束的条件：
当 k > n 时，说明所有位置都已经填好了，此时输出当前排列，然后结束本次递归。
setw(5) 是题目要求的输出格式，表示每个数字占 5 个字符宽度。
接下来是最重要的部分：
我们逐行理解。
① 判断数字能否使用
如果数字 i 已经出现在当前排列中，就跳过它。
② 把数字放到当前位置
把数字 i 放到第 k 个位置，并标记它已经使用。
③ 递归填写下一个位置
当前位置已经确定，接下来继续填写第 k+1 个位置。
④ 恢复现场
这是最容易忘记的一行。
注意，执行到这里时，dfs(k + 1) 已经返回，说明以数字 i 放在当前位置的所有排列，都已经搜索完了。
现在要换一个数字放在当前位置，所以需要把刚才的使用标记取消。
这样其他排列才能继续使用数字 i。
这个过程可以简单记为：
选一个数 → 标记 → 递归 → 取消标记。
这四步就是全排列 DFS 最重要的部分。
另外，由于每次都按照从小到大的顺序尝试数字，所以输出的排列自然满足字典序要求。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、第二道题：P1008 三连击
题目链接：https://www.luogu.com.cn/problem/P1008
这是一道 NOIP 1998 普及组真题。
题目要求
使用数字 1 到 9，每个数字恰好使用一次，组成三个三位数 A、B、C。
要求三个数字满足：
A : B : C = 1 : 2 : 3
输出所有符合要求的方案。
解题思路
我们可以直接枚举 1 到 9 的所有排列。
对于每一种完整排列，把它分成三段：
然后判断 B 是否等于 A 的两倍，C 是否等于 A 的三倍。
满足条件就输出，否则继续尝试下一种排列。
参考代码
与上一题有什么区别？
仔细观察，你会发现两道题的 DFS 部分几乎完全相同。
区别只在递归结束后：
* P1706：直接输出当前排列。
* P1008：先判断当前排列是否满足条件，满足才输出。
这就是全排列 DFS 很实用的地方。
DFS 负责枚举所有可能的方案，至于如何判断、计算答案，则由具体题目决定。
本题最多需要枚举 9! = 362880 种排列，可以直接通过暴力搜索解决。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、第三道题：P1433 吃奶酪——实战骗分
题目链接：https://www.luogu.com.cn/problem/P1433
前面两道题都能够通过全部数据。
现在我们来看一道正解比较困难，但可以使用 DFS 解决小规模数据的题目。
题目要求
平面上有 n 块奶酪，每块奶酪都有一个坐标。
一只老鼠从 (0, 0) 出发，需要吃完所有奶酪。
老鼠可以自由决定吃奶酪的顺序，要求走过的总距离最短。
数据范围：1 ≤ n ≤ 15。
先考虑暴力做法
题目要求最短距离，但我们不知道按照什么顺序访问奶酪才是最优的。
既然不知道，那就把所有顺序都试一遍。
假设奶酪编号为 1 到 n：
1. DFS 枚举下一块访问的奶酪。
2. 计算本次移动的距离。
3. 继续访问剩余奶酪。
4. 全部访问完后，更新最短距离。
这和之前的全排列没有本质区别。
只不过以前是输出排列，现在是计算排列对应的总路程。
递归函数怎么设计？
这次需要记录更多信息：
其中：
* k：准备访问第几块奶酪。
* last：当前所在位置的编号。
* sum：已经走过的距离。
每次选择下一块奶酪，就把移动距离加到 sum 中。
为了方便计算，我们提前使用 d[i][j] 保存从第 i 个位置到第 j 个位置的距离。
其中，编号 0 表示起点 (0, 0)。
参考代码
看懂关键代码
先看递归：
假设我们决定下一步访问第 i 块奶酪。
先标记第 i 块奶酪已经访问，然后递归进入下一层。
递归时要修改两个参数：
* last 变成 i，因为老鼠现在到了第 i 块奶酪。
* sum 加上 d[last][i]，因为老鼠又走了一段路。
返回后，取消使用标记，再尝试访问其他奶酪。
注意这里不需要再写一个 sum -= ...。
因为 sum 是函数参数，递归调用中的新距离不会直接修改上一层的 sum。
接下来是这两行：
当所有奶酪都吃完时，当前的 sum 就是一条完整路线的总距离。
我们不断更新 ans，就能找到搜索过的路线中最短的一条。
为什么要加剪枝？
观察递归开头：
假设目前找到的最短路线是 20。
现在另一条路线还没走完，就已经走了 25。
那么这条路线还有必要继续搜索吗？
显然没有。
因为剩下的路程不可能是负数，即使继续走，也不可能比 20 更短。
因此可以直接 return，不再搜索这条路线后面的情况。
这种提前放弃无用搜索的操作叫作剪枝。
剪枝能够减少搜索量，但并不能保证这道题的全部数据都能通过。
这道题为什么能骗分？
本题最大有 15 块奶酪。
如果全部枚举，一共有：
15! = 1,307,674,368,000
超过一万亿种访问顺序，纯暴力搜索显然很难在时间限制内完成。
但如果 n = 8，只有 40320 种排列，暴力就很容易处理。
所以这份 DFS 程序虽然不能保证通过全部数据，但可以正确处理小规模测试点。
在按测试点计分的情况下，只要这些小规模测试点独立给分，就有机会拿到部分分数。
具体能拿多少分，还要看题目的测试数据和评分规则，不能保证固定分数。
七、比赛中怎么判断能不能用全排列？
全排列的最大问题是：排列数量增长得很快。
n 排列数量 6 720 7 5,040 8 40,320 9 362,880 10 3,628,800 11 39,916,800 12 479,001,600 15 1,307,674,368,000
假设每一种排列还需要检查 n 个元素，那么时间复杂度通常是 O(n × n!)。
比赛中可以这样判断：
* n ≤ 8：一般可以直接尝试全排列。
* n = 9 或 10：要考虑每种排列的计算量。
* n ≥ 11：完整枚举通常就比较困难了。
这只是经验，实际能否通过还取决于时间限制、剪枝效果等因素。
判断是否值得写全排列，重点看题目是否涉及元素的排列顺序，以及小规模数据有多大。
如果遇到不会做的题，可以按这个顺序考虑：
1. 看题目是否要求安排顺序、重新排列或访问全部对象。
2. 想一想能否枚举所有顺序，并计算每种顺序的答案。
3. 看数据范围及部分分说明，判断小规模数据能否使用全排列。
如果可以，就先写出正确的暴力程序，不要因为暂时不会正解而放弃能拿到的分数。
八、比赛中最需要记住的模板
这份模板适用于从 1 到 n 中选择数字、每个数字恰好使用一次的全排列问题。
实际比赛时，通常只需要修改两个地方：
第一个地方：递归结束时做什么。
可以输出排列、判断方案是否合法，或者计算最优答案。
第二个地方：递归需要记录哪些信息。
如果只是输出排列，一个参数 k 就够了。
如果需要计算路径长度、费用等信息，可以像 P1433 一样增加参数。
不论题目怎么变化，最基本的 DFS 过程始终是：
最后还要特别注意两件事：
第一，递归结束之后，必须取消使用标记，否则会漏掉其他排列。
第二，dfs 并不一定能通过全部数据。考试时要根据数据范围判断，能拿多少部分分就先争取多少。
九、课后练习
按顺序完成下面三道题：
1. P1706 全排列问题：掌握 DFS 和回溯模板。
2. P1008 三连击：枚举所有排列，筛选合法答案。
3. P1433 吃奶酪：使用 DFS 寻找最短路径，理解全排列暴力的适用范围。
学完这一节，最重要的不是记住某道题的答案，而是能够在遇到顺序安排类问题时，自己想到：
先用 DFS 把所有可能的排列搜索出来，再根据题目要求判断或计算答案。
这是全排列搜索的基本用法，也是竞赛中争取暴力分数的一种实用方法。
