DFS/BFS以及剪枝技巧
DFS简介
DFS含义 ⭐
DFS，即Depth-first-search，是深度优先搜索的简称。
它的主要思路是一直沿当前分支搜索，当搜索到尽头之后返回，再逐步向其他地方扩散。
我们可以通过一个树形结构说明DFS的遍历顺序
1 | A |
遍历顺序：(假设一直沿左分支走)
A→B→E→H→I→F→C→D→G
当然，完全可以沿右分支先走，甚至遍历起点并不非得是树的顶端。
事实上，DFS的实现依赖于递归，而遍历的顺序也和递归的位置息息相关。
甚至通过调整递归的顺序，我们可以用三种方法遍历一个二叉树，不过这并不是本次重点，不过多叙述
接下来让我们通过一个简单的例题来看看DFS的实现。
全球变暖
题目描述
你有一张某海域 $N \times N$ 像素的照片，. 表示海洋、 # 表示陆地，如下所示：
1 | ....... |
其中 “上下左右” 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 $2$ 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。
例如上图中的海域未来会变成如下样子：
1 | ....... |
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数 $N$。$(1 \le N \le 1000)$。
以下 $N$ 行 $N$ 列代表一张海域照片。
照片保证第 $1$ 行、第 $1$ 列、第 $N$ 行、第 $N$ 列的像素都是海洋。
输出格式
一个整数表示答案。
输入输出样例 #1
输入 #1
1 | 7 |
输出 #1
1 | 1 |
说明/提示
时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛
题解
这是一个连通性问题，要把图内所有联通的点都遍历一次，可以使用DFS去遍历。
DFS遍历的格式大概是1
2
3
4
5
6
7
8
9
10
11
12
13void dfs(){
if(已遍历完){
记录
return;
}
for(...){//枚举情况
if(遍历过)
continue;
记录此点
dfs();
回溯
}
}
观察可知，此题需要我们不断向四周扩散记录联通区域。
解题思路大概是：
先对输入数据预处理，令我们可以通过二维数组中的值得知这块陆地周围有几个岛屿。
然后每次检查，都把一整片岛屿标记为已检查，在这个过程中寻找有没有周围有四块陆地的点。如果有，说明这个岛屿不会被淹没。
而这个检查的过程就可以通过DFS递归来实现：
每次检查完一块陆地都检查这块陆地周围的陆地有没有 $4$
最后达到同时遍历一整块岛屿的效果。
其中，关键在于DFS递归时的退出条件以及正确清空已经遍历过的岛屿，避免死循环。
代码
1 |
|
P2196 [NOIP 1996 提高组] 挖地雷
P2196 [NOIP 1996 提高组] 挖地雷
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
int n,value[21],vis[21];
vector<int> p[21];
int ans=0;vector<int>ansRoute;
void dfs(int start,int nowTotal,vector<int>nowRoute){
vector<int>& Tos=p[start];
int flag=1;
for(int len=Tos.size(),i=0;i<len;i++){
if(vis[Tos[i]])
continue;
flag=0;
nowRoute.push_back(Tos[i]);
vis[Tos[i]]=1;
dfs(Tos[i],nowTotal+value[Tos[i]],nowRoute);
vis[Tos[i]]=0;
nowRoute.pop_back();
}
if(flag){
if(ans<nowTotal){
ansRoute=nowRoute;
ans=nowTotal;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>value[i];
}
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
bool a;
cin>>a;
if(a){
p[i].push_back(j);
// p[j].push_back(i);
}
}
}
for(int i=1;i<=n;i++){
vector<int> tempRoute={i};
vis[i]=1;
dfs(i,value[i],tempRoute);
vis[i]=0;
}
for(auto& a:ansRoute){
cout<<a<<" ";
}
cout<<endl<<ans;
return 0;
}
DFS练习题目
建议看完剪枝技巧再做其中难度较高的题
P1219八皇后
P1019单词接龙
P5194 Scales S
BFS简介 ⭐⭐
BFS含义
BFS指广度优先搜索。与DFS的区别在于，bfs的遍历顺序并不是优先搜索到分支的尽头，而是先遍历完当前层的全部节点，再扩散到下一层。
这样的好处在于，并不需要遍历完一整个分支，而是尽可能判断多个分支，在解决最短路径问题时十分优越，因为在找到最短路径后就可以退出。
让我们通过一个简单的树形结构观察一下BFS的遍历顺序1
2
3
4
5
6
7 A
/ | \
B C D
/ \ |
E F G
/ \
H I
遍历顺序：A→B→C→D→E→F→G→H→I
显然 BFS在遍历到 $C$ 的时候就会发现，这是目前最短的路径，因此BFS在完成最短路径，最少步数问题时更为便捷。
我们还是通过同一个例题来看看BFS如何实现，以便感受DFS和BFS的相同与不同
全球变暖
题干请看上一节，不再赘述。
题解
DFS的实现依赖于递归，也就是栈，先进后出。
相应的，BFD的实现依赖于队列，先进先出。
对于每个节点，BFS会先把当前节点出队，然后把该节点的全部子节点入队，如此反复直到队列为空。
这样可以保证队列中永远只有两层节点，因为父层节点遍历完之后子层节点才会开始弹出并放入新的子节点。
对于全球变暖这道题来说，BFS就是不断把陆地弹出，然后把这个陆地联通的的全部陆地入队。在这个过程中不断标记那些节点已经访问过，就实现了BFS遍历联通的全部陆地。
在BFS的实现中，因为父节点与子节点紧密练习，所以只需要观察当前陆地联通的四块是不是都是陆地就可以判断有没有被淹没。
注意标记是否访问过数组上的点。
1 |
|
剪枝技巧 ⭐⭐⭐⭐
⭐表示难度：
可行性剪枝 ⭐
Count that cows
FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 $x$ 和 $y$，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 $2\times x$ 的位置。计算他至少需要几步追上他的牛。
第一行为一个整数 $t\ ( 1\le t\le 10)$，表示数据组数；
接下来每行包含一个两个正整数 $x,y\ (0<x,y \le 10^5)$，分别表示 FJ 和牛的坐标。
对于每组数据，输出最少步数。
输入：
1 | 1 |
输出：
1 | 4 |
题解：
可行性剪枝是最为简单、直观的一种剪枝技巧。
即使没有特意学过剪枝，只接触过基本的DFS与BFS概念的同学也可能独立想出。
其本质是：确定当前情况已经不合法，就不需要再做剩下的“无谓”运算去寻找答案，而是直接把这一分支砍掉。
在本题中，显然当位置小于牛时，可以选择进一步，退一步和乘二，它们分别代表三种可能性。
但当位置大于牛时，无论是进一步还是乘二，都不可能接近答案，因此这是“不可行”的分支，需要砍去。
本题也利用了哈希表去判重剪枝，具体可参考下面的BFS去重剪枝
代码：
1 |
|
最优性剪枝 ⭐⭐⭐
P1118 [USACO06FEB] Backward Digit Sums G/S
题目描述
游戏描述
有这么一个游戏：
写出一个 $1 \sim n$ 的排列 $a$，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作。
显然每次构成的序列都比上一次的序列长度少 $1$，直到只剩下一个数字位置。
1 | 3 1 2 4 |
任务要求
现在要倒着玩这个游戏。如果知道 $n$ 和最终得到的数字的大小 sum，请你求出最初的序列 $a$。
注意：如果有多种答案，要求输出字典序最小的那一个。
字典序
我们称序列 $a = \langle a_1, a_2, \dots, a_n \rangle$ 的字典序小于序列 $b = \langle b_1, b_2, \dots, b_n \rangle$ 的字典序，当且仅当存在一个位置 $p$，满足：
$a1 = b_1, a_2 = b_2, \dots, a{p-1} = b_{p-1}$，
且 $a_p < b_p$。
输入：共一行两个正整数 $n,sum$。
输出：输出包括一行，为字典序最小的那个答案。
当无解的时候，请什么也不输出。
输入 #1
1 | 4 16 |
输出 #1
1 | 3 1 2 4 |
说明/提示
- 对于 $40\%$ 的数据，$1\le n\le 7$；
- 对于 $80\%$ 的数据，$1\le n \le 10$；
- 对于 $100\%$ 的数据，$1\le n \le 12$，$1\le sum\le 12345$。
题解：
本题主要运用的剪枝技巧是对杨辉三角预处理，以及最优性剪枝。
对杨辉三角的预处理是在于，如果需要调用组合数的话，可以先把杨辉三角存入全局数组方便调用，不多赘述。
最优性剪枝指 如果当前答案的最大可能值都无法超过目前的最优答案，那么就可以直接舍弃当前分支。
这是一种求解最优问题的剪枝思路。
回到本题，本题思路大概是：通过dfs对1到n的数字全排列，当其杨辉三角和为sum时即找到正确答案。
dfs从小到大遍历可保证第一个答案是字典序最小的答案。
最优化剪枝的应用在于对目前截取出来的数字串进行处理，计算其可能的值，若目前列出的值已经超过sum，则应当剪去该分支。
1 |
|
BFS判重剪枝 ⭐⭐
0跳蚂蚱 蓝桥杯2017
此题是一个简单的八数码问题：
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下图所示：
（插入图片）
有 9 只盘子，排成 1 个圆圈。其中 8 只盘子内装着 8 只蚱蜢，有一个是空盘。
我们把这些蚱蜢顺时针编号为 1 ~ 8。
规则
每只蚱蜢都可以：
跳到相邻的空盘中。
也可以用力一点，越过一个相邻的蚱蜢 跳到空盘中。
目标
请计算至少要经过多少次跳跃，才能使蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变。
题解
我们可以将问题视作是空盘与相邻盘的置换，每次有四种置换的可能。
不断置换，得到答案后返回。
求解最短次数，显然用BFS解决。
但是，假如空盘与右边盘子互换后，又与左侧盘子互换。左换右，右换左，无穷无尽，陷入死循环。
因此我们需要判断一种可能性有没有出现过，如果它出现过，那么它延伸出的所有分支都会位于队列中，不需要重复计算。
可以使用哈希表解决这个问题。
另外，计算BFS复杂问题的步数时，可以采用pair或结构体记载层数。
代码：
1 |
|
搜索顺序剪枝 ⭐⭐⭐
P1164 小A点菜
此题不是搜索题，但是可以根据题意领略一些如何优化搜索顺序
因为有hack数据，所以无法使用搜索得到满分1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using namespace std;
int n,m,food[105];
long long ans;
void dfs(int start,int canUseMoney){//现在有这么多钱，从start+1开始选择
if(canUseMoney<0)
return;
else if(canUseMoney==0){
ans++;
return;
}
for(int i=start+1;i<=n;i++){
dfs(i,canUseMoney-food[i]);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>food[i];
sort(food+1,food+n+1,greater<int>());
for(int i=1;i<=n;i++){
dfs(i,m-food[i]);
}
cout<<ans;
return 0;
}
P1120小木棍:较难
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 $50$。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入格式
第一行是一个整数 $n$，表示小木棍的个数。
第二行有 $n$ 个整数，表示各个木棍的长度 $a_i$。
输出格式
输出一行一个整数表示答案。
输入 #11
29
5 2 1 5 2 1 5 2 1
输出 #1
1 | 6 |
对于全部测试点，$1 \leq n \leq 65$，$1 \leq a_i \leq 50$。
题解
阅读题干，想到尝试暴力深搜，只需要把每个可能的长度枚举出来，对每个长度进行DFS，看看能否拼接成全部是这个长度的长木棍即可。
如果全部都成功拼接，则输出答案，如果不行，则继续搜索。
此题关键在于暴力搜索的时间复杂度过高，需要极强的剪枝技巧。
搜索顺序剪枝是指，按一定的顺序去搜索，可以有效避免产生大量的无效分支。
对于本题而言，无论木棍长短，都总是要拼接进去的，那么如果先尝试长的小木棍，就可以快速把长度积累到目标值附近，或者直接判断出不可能拼接出目标值（若目标值太小）。
而把小木棍放前面则会产生大量冗杂的可能性。
因此，可以先对数组进行降序处理，再继续DFS搜索。
此外。本题还有很多独属于此题的剪枝技巧，因为没有太多的可重复性，所以在此仅简单提及，有兴趣的同学可以观看洛谷题解：
1、排序之后可以通过预处理出next数组，假如一个长度的小木棍不符合，就快速跳到下一个长度的木棍区间，而不是一个一个检索。
2、若本次恰好可以组成一个长木棍，但是后面的拼接失败了，那么不需要在本次DFS的基础之上再搜索，而是直接return。
因为把恰好能组成木棍的放入必然是最优解，如果这样都不行，那无论怎么调整都是不行的。
3、先把可能的答案预处理一下，因为答案只可能是总和的因数。
从小到大检查答案，检查到的第一个一定是最小的，直接输出即可。
1 |
|
