docs/search/backtracking.md
本页面将简要介绍回溯法的概念和应用．
回溯法是一种经常被用在 深度优先搜索（DFS） 和 广度优先搜索（BFS） 的技巧．
其本质是：走不通就回头．
构造空间树；
进行遍历；
如遇到边界条件，即不再向下搜索，转而搜索另一条链；
达到目标条件，输出结果．
???+ example "USACO 1.5.4 Checker Challenge" 现在有一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行，每列，每条对角线（包括两条主对角线的所有对角线）上都至多有一个棋子．
```plain
0 1 2 3 4 5 6
-------------------------
1 | | O | | | | |
-------------------------
2 | | | | O | | |
-------------------------
3 | | | | | | O |
-------------------------
4 | O | | | | | |
-------------------------
5 | | | O | | | |
-------------------------
6 | | | | | O | |
-------------------------
```
上面的布局可以用序列 $\{2,4,6,1,3,5\}$ 来描述，第 $i$ 个数字表示在第 $i$ 行的第 $a_i$ 列有一个棋子，如下所示
行号 $i$：$\{1,2,3,4,5,6\}$
列号 $a_i$：$\{2,4,6,1,3,5\}$
这只是跳棋放置的一个方案．请编一个程序找出所有方案并把它们以上面的序列化方法输出，按字典顺序排列．你只需输出前 $3$ 个解并在最后一行输出解的总个数．特别注意：你需要优化你的程序以保证在更大棋盘尺寸下的程序效率．
??? note "参考代码"
cpp --8<-- "docs/search/code/backtracking/backtracking_1.cpp"
???+ example "迷宫" 现有一个尺寸为 $N \times M$ 的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过．给定起点坐标和终点坐标，且每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案．在迷宫中移动有上、下、左、右四种移动方式，每次只能移动一个方格．数据保证起点上没有障碍．
??? note "参考代码"
cpp --8<-- "docs/search/code/backtracking/backtracking_2.cpp"