# DFS

# 递归和记忆化搜索

	1 #include<bits/stdc++.h>
	2 using namespace std;
	3 int cnt=0; // 统计执行了多少次递归
	4 int data[25]; // 存储斐波那契数
	5 int fib (int n){
	6 cnt++;
	7 if (n == 1 \|\| n == 2) { data[n]=1; return data[n]; }
	8 if(data[n]!=0) return data[n]; // 记忆化判断：已经算过，不用再算，直接返回结果
	9 data[n] = fib (n-1) + fib (n-2); // 继续递归
	10 return data[n];
	11 }
	12 int main(){
	13 cout << fib(20); // 计算第 20 个斐波那契数
	14 cout <<”cnt=”<<cnt; // 递归了 cnt=37 次
	15 }

# DFS 代码框架

 1  ans;                                 //答案，用全局变量表示
 2  void dfs（层数，其他参数）{
 3      if （出局判断){                    //到达最底层，或者满足条件退出 
 4          更新答案;                     //答案一般用全局变量表示
 5          return;                      //返回到上一层
 6      }
 7      （剪枝）                           //在进一步DFS之前剪枝
 8      for （枚举下一层可能的情况）          //对每一种情况继续DFS 
 9          if (used[i] == 0) {          //如果状态i没有用过，就可以进入下一层
10              used[i] = 1;             //标记状态i，表示已经用过，在更底层不能再使用
11              dfs（层数+1，其他参数）;     //下一层 
12              used[i] = 0;             //恢复状态，回溯时，不影响上一层对这个状态的使用
13              }
14      return;                          //返回到上一层
15  }

# DFS 的所有路径

如果搜索所有的路径，应该用 DFS；如果只搜索最短的路径，则应该用 BFS。

# 题目：输出所有路径

【题目描述】给出一张图，输出从起点到终点的所有路径。

【输入描述】输入的第一行是整数 n、m，分别是行数和列数。后面的 n 行，每行有 m 个符号。“@” 表示起点，“*” 表示终点，“・” 表示能走，“#” 表示是墙壁不能走。每一步都按左→上→右→下的顺序搜索。在样例中，左上角坐标为 (0,0)，起点坐标为 (1, 1)，终点坐标为 (0, 2)。1<n, m <7。

【输出描述】输出所有的路径。坐标 (i, j) 用 ij 表示，例如坐标 (0, 2) 表示为 02。从左到右是 i，从上到下是 j。

	1 #include<bits/stdc++.h>
	2 using namespace std;
	3 char mp[10][10]; // 地图
	4 string p[10][10]; // 记录从起点到点 path [i][j] 的路径
	5 int d[4][2] = <!--swig0-->; // 左、上、右、下。左上角坐标是 (0,0)
	6 int Wy, Hx, num=0; //Wy 行，Hx 列。用 num 统计路径数量
	7 int sx,sy,tx,ty; // 起点和终点
	8 void dfs(int x, int y){
	9 for(int i = 0; i < 4; i++) { // 左、上、右、下，沿 4 个方向顺时针 DFS
	10 int nx=x+d[i][0], ny=y+d[i][1]; // 一个邻居点
	11 if(nx>=Hx \|\| nx<0 \|\| ny <0 \|\| ny>=Wy) continue; // 不在地图内
	12 if(mp[nx][ny] == ‘*’) { // 遇到终点
	13 num++;
	14 char t[4]; sprintf(t, “%d%d”,nx,ny); // 记录路径
	15 cout<<num<<”: “<<p[x][y]+ “->”+t<<”\n”; // 输出路径
	16 continue; // 不退出，继续找下一条路径
	17 }
	18 if( mp[nx][ny] == ‘. ‘){
	19 mp[nx][ny] = ‘#’; // 保存现场。这个点在这次更深的 DFS 中不能再用
	20 char t[4];sprintf(t, “%d%d”,nx,ny);p[nx][ny]=p[x][y]+ “->”+t; // 记录路径
	21 dfs(nx, ny);
	22 mp[nx][ny] = ‘. ‘; // 恢复现场。回溯之后，这个点可以再用
	23 }
	24 }
	25 }
	26 int main(){
	27 cin >> Wy >> Hx; //Wy 行，Hx 列
	28 for (int y = 0; y < Wy; y++) { // 有 Hx 列
	29 for (int x = 0; x < Hx; x++) { // 一次读入一行
	30 cin >> mp[x][y];
	31 if(mp[x][y]== ‘@’) {sx=x; sy=y;} // 读起点
	32 if(mp[x][y]== ‘*’) {tx=x; ty=y;} // 读终点
	33 }
	34 }
	35 cout<<”from “<<sx<<sy<<” to “<<tx<<ty<<”\n”;
	36 char t[4]; sprintf(t, “%d%d”, sx,sy); p[sx][sy] = t; // 开始记录路径
	37 dfs(sx, sy); // 搜索并输出所有路径
	38 //cout<<num; // 输出路径总数
	39 return 0;
	40 }

# DFS 与排列组合

# 自写排列算法 1

(1) 让第一个数不同，得到 n 个数列。其办法是把第 1 个数和后面每个数交换。

(2) 在上面的每个数列中，去掉第一个数，对后面的 n−1 个数进行类似的排列。

(3) 重复以上步骤，直到用完所有数字。

	1 #include<bits/stdc++.h>
	2 using namespace std;
	3 int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
	4 void dfs(int s, int t){ // 从第 s 个数开始到第 t 个数结束的全排列
	5 if(s==t) { // 递归结束，产生一个全排列
	6 for(int i=0; i<=t; ++i) cout <<a[i]<< “ “; // 输出一个排列
	7 cout<<”; “;
	8 return;
	9 }
	10 for(int i=s; i<=t; i++) {
	11 swap(a[s], a[i]); // 把当前第 1 个数与后面所有数交换位置
	12 dfs(s+1, t);
	13 swap(a[s], a[i]); // 恢复，用于下一次交换
	14 }
	15 }
	16 int main(){
	17 int n = 3;
	18 dfs(0, n-1); // 前 n 个数的全排列
	19 }

上述代码运行后输出：“1 2 3；1 3 2；2 1 3；2 3 1；3 2 1；3 1 2；”。

如果需要打印 n 个数中任意 m 个数的排列，例如在 4 个数中取任意 3 个数的排列，则可以将上面代码中的第 17 行改为 n = 4，然后在 dfs () 中只修改第 5、6 行。下面给出完整代码。

	1 #include<bits/stdc++.h>
	2 using namespace std;
	3 int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
	4 void dfs(int s, int t){
	5 if(s==3) { // 改为 s==3
	6 for(int i=0; i<3; ++i) cout <<a[i]<< “ “; // 改为 i<3
	7 cout<<”; “;
	8 return;
	9 }
	10 for(int i=s; i<=t; i++) {
	11 swap(a[s], a[i]);
	12 dfs(s+1, t);
	13 swap(a[s], a[i]);
	14 }
	15 }
	16 int main(){
	17 int n = 4;
	18 dfs(0, n-1); // 前 n 个数的全排列
	19 }

上面的代码很短很简单，但是不能按从小到大的顺序输出排列。

# 自写排列算法 2

下面的代码能按从小到大的顺序输出排列。前提是 a [20] 中的数字是从小到大排列的，如果不是，就需要先排序。

用 b [] 记录一个新的全排列，第一次进入 dfs () 时，b [0] 在 n 个数中选一个数，第二次进入 dfs () 时，b [1] 在剩下的 n−1 个数中选一个数，等等。用 vis [] 记录某个数是否已经被选过，被选过的数不能在后面继续被选。

	1 #include<bits/stdc++.h>
	2 using namespace std;
	3 int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
	4 bool vis[20]; // 记录第 i 个数是否用过
	5 int b[20]; // 生成的一个全排列
	6 void dfs(int s,int t){
	7 if(s==t) { // 递归结束，产生一个全排列
	8 for(int i=0; i<t; ++i) cout<<b[i]<< “ “; // 输出一个排列
	9 cout<<”; “;
	10 return;
	11 }
	12 for(int i=0;i<t;i++)
	13 if(!vis[i]){
	14 vis[i]=True;
	15 b[s]=a[i];
	16 dfs(s+1,t);
	17 vis[i]=False;
	18 }
	19 }
	20 int main(){
	21 int n=3;
	22 dfs(0,n); // 前 n 个数的全排列
	23 return 0;
	24 }

	1 #include<bits/stdc++.h>
	2 using namespace std;
	3 int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
	4 bool vis[20];
	5 int b[20];
	6 void dfs(int s,int t){
	7 if(s==3) { // 改为 s==3
	8 for(int i=0; i<3; ++i) cout<<b[i]<< “ “; // 改为 i<3
	9 cout<<”; “;
	10 return;
	11 }
	12 for(int i=0;i<t;i++)
	13 if(!vis[i]){
	14 vis[i]=True;
	15 b[s]=a[i];
	16 dfs(s+1,t);
	17 vis[i]=False;
	18 }
	19 }
	20 int main(){
	21 int n=4;
	22 dfs(0,n); // 前 n 个数的全排列
	23 return 0;
	24 }

# 自写组合算法

用 DFS 可以很巧妙地输出组合。进行 DFS 时，选或不选第 k 个数，就可以实现各种组合。

	1 #include<bits/stdc++.h>
	2 using namespace std;
	3 int a[]={1,2,3,4,5,6,7,8,9,10};
	4 int vis[10];
	5 void dfs(int k) {
	6 if (k == 3) {
	7 for(int i=0;i<3;i++)
	8 if(vis[i]) cout<<a[i];
	9 cout<<”-”;
	10 }
	11 else {
	12 vis[k] = 0; // 不选中第 k 个数
	13 dfs(k + 1); // 继续搜下一个数
	14 vis[k] = 1; // 选这个数
	15 dfs(k + 1); // 继续搜下一个数
	16 }
	17 }
	18 int main() {
	19 dfs(0); // 从第一个数开始
	20 return 0;
	21 }

# BFS 基础

BFS 的原理是 “逐层扩散”，从起点出发按层次先后搜索。编程时，BFS 用队列实现。由于 BFS 的特点是逐层搜索，先搜到的层离起点更近，所以 BFS 一般用于求解最短路径问题。

# BFS 与最短路径

计算最短路径是 BFS 的基本应用。BFS 是一种很好的查找最短路径的算法，不过它只适合一种情况：任意相邻两点之间的距离相等，一般把这个距离看成 1，有时称为 1 跳。在这种情况下，要查找一个起点到一个终点的最短距离，BFS 是最优的查找最短路径的算法，计算复杂度是 O (n+m)，n 是图上点的数量，m 是边数。

(1) 最短路径有多长。要注意最短路径的长度是唯一的。

(2) 最短路径经过了哪些点。由于最短路径可能不只一条，所以题目一般不要求输出路径。如果要求输出路径，则一般输出字典序最小的那条路径。

# 连通性判断

连通性判断是图论中的一个简单问题，给定一张图，图由点和连接点的边组成，要求找到图中互相连通的部分。这是基础的搜索，用 DFS 或 BFS 都行。

# DFS 连通性判断

(1) 从图上任意一个点 u 开始遍历，标记点 u 已经被搜索过。

(2) 递归点 u 的所有符合连通条件的邻居点。

(3) 递归结束，找到了与点 u 连通的所有点，这是一个连通块。

(4) 不与点 u 连通的、其他没有访问到的点，继续用上述步骤处理，直到找到所有的连通块。

# BFS 连通性判断

(1) 从图上任意一个点 u 开始遍历，把它放进队列中。

(2) 弹出队首 u，标记点 u 已经被搜索过，然后搜索点 u 的邻居点，即与点 u 连通的点，将其放到队列中。

(3) 弹出队首，标记为已被搜索过，然后搜索与它连通的邻居点，放进队列。

# BFS 与判重

BFS 的题目很多与判重有关。BFS 的原理是逐步扩展下一层，把扩展出的下一层点放进队列中处理。在任意时刻，队列中只包含相邻两层的点。大家自然会想到这样一系列问题：这两层的点会不会太多了，队列放不放得下，即使队列放得下，太多的点会不会影响计算量。

(1) 如果这些点互不相同，那么没有办法，只能把所有点放进队列。

(2) 如果这些点有相同的，那么只搜索一次就够了，其他相同的点不用再搜索。此时需要判重。

(1) map 判重

2) set 判重

# 双向广搜

设想有这样一个搜索场景：有确定的起点 s 和终点 t，并且能把从起点到终点的单向搜索变换为分别从起点出发和从终点出发的 “相遇” 问题。此时可以进行以下优化操作：从起点 s（正向搜索）和终点 t（逆向搜索）同时开始搜索，当两个搜索产生相同的一个子状态 v 时就结束搜索。v 是相遇点，得到的 s-v-t 是一条最佳路径，当然，最佳路径可能不止这一条。注意，和普通 BFS 一样，双向广搜在搜索时并没有 “方向感”，所谓 “正向搜索” 和 “逆向搜索” 其实是盲目的，它们表示分别从 s 和 t 逐层扩散出去，直到相遇为止。

# 剪枝

BFS 的主要剪枝技术是判重，如果搜索到某一层时出现重复的状态，就剪枝。

DFS 的剪枝技术较多，有可行性剪枝、搜索顺序剪枝、最优性剪枝、排除等效冗余、记忆化搜索等，下面分别进行简单介绍。

(1) 可行性剪枝：对当前状态进行检查，如果当前条件不合法就不再继续，直接返回。

(2) 搜索顺序剪枝：搜索树有多个层次和分支，不同的搜索顺序会产生不同的搜索树形态，复杂度也相差很大。

(3) 最优性剪枝：在最优化问题的搜索过程中，如果当前花费的代价已超过前面搜索到的最优解，那么本次搜索就没有继续进行下去的意义了，此时停止对当前分支的搜索，进行回溯。

(4) 排除等效冗余：搜索的不同分支，最后的结果是一样的，那么只搜一个分支就够了。

(5) 记忆化搜索：在递归的过程中，有许多分支被反复计算，会大大降低算法的执行效率。用记忆化搜索将已经计算出来的结果保存起来，以后需要用到的时候直接取出结果，避免重复运算，从而提高算法的效率。记忆化搜索将在 DP 相关内容中讲解。

(1)“迷宫” lanqiaoOJ 题号 641。题目大意：迷宫内每个点都有一个人，问有多少人能走出来。剪枝：可使用记忆化搜索，如果一个点已被搜索过，就不用再搜索。

(2)“方格分割” lanqiaoOJ 题号 644。题目大意：把 6×6 的方格分割成完全相同的两部分，问有多少种分割方法。剪枝：从中心点开始分割，分割的时候注意不能同时分割关于中心点的两个点，用到了可行性剪枝；也用到了记忆化搜索，即标记点是否被访问过。

(3)“寒假作业” lanqiaoOJ 题号 1388。题目大意：把数字不重复地填写到 4 个式子中，实现加、减、乘、除运算。剪枝：如果第一个式子中填写的数字不满足等式，后面就不用填写了，这用到了可行性剪枝。

(4)“全球变暖” lanqiaoOJ 题号 178。题目大意：问有多少座岛屿被淹没。剪枝：可使用记忆化搜索，被检查过的点不用再检查。

(5)“跳蚱蜢” lanqiaoOJ 题号 642。题目大意：从一种状态跳到另一种状态，问至少要跳多少次。剪枝：可使用判重。

(6)“迷宫” lanqiaoOJ 题号 602。题目大意：找到最短路径。剪枝：可使用最优性剪枝，找字典序最短的路径。下面给出一些剪枝的题目，帮助读者深入理解。

比赛