【算法】蓝桥杯dfs深度优先搜索之凑算式总结
本文 → 《【算法】蓝桥杯dfs深度优先搜索之凑算式总结》
相关文章 →《【算法】蓝桥杯dfs深度优先搜索之排列组合总结》
前言
曾几何时这个词现在用正适合不过了。
曾几何时我还是对dfs算法一脸懵x的状态，虽说大二的时候学过数据结构，但是那一学期被我荒废了......详情等我毕业了再说吧。
还有四天就要考蓝桥杯了，我分析了近四年的蓝桥杯（B组）题型，分类纯属个人理解，并非官方宣布，如下表：
注：
以下DFS代表Depth First Search首字母缩写，即深度优先搜索，简称深搜
以下DP代表Dynamic Programming首字母缩写，即动态规划，没有简称 : )
2015年（第六届）蓝桥杯B组省赛 | 分类| 题号| 总分 |
| --- | --- | --- |
|---|---|---|
| DFS/爆破 | 3（9分）、5（15分）、7（21分） | 45分 |
| 冒泡 （加法乘法） | 6（17分） | 17分 |
| 取余 （饮料换购） | 8（13分） | 13分 |
| 矩阵 | 9（25分） | 25分 |
| DP | 10（31分） | 31分 |
2016年（第七届）蓝桥杯B组省赛 | 分类| 题号| 总分 |
| --- | --- | --- |
|---|---|---|
| 函数调用 | 4（11分） | 11分 |
| DFS/爆破 | 3（9分）、5（13分）、 6（15分）、7（19分）、 8（21分） | 77分 |
| DP | 9（23分） | 23分 |
| 数据结构 | 10（31分） | 31分 |
2017年（第八届）蓝桥杯B组省赛 | 分类| 题号| 总分 |
| --- | --- | --- |
|---|---|---|
| DFS/爆破 | 2（11分）、4（17分） | 28分 |
| 水题 | 5（7分） | 7分 |
| DP | 6（9分）、8（21分） | 30分 |
| 日期问题 | 7（19分） | 19分 |
| 二分问题 | 9（23分） | 23分 |
| 前缀和 | 10（25分） | 25分 |
2018年（第九届）蓝桥杯B组省赛 | 分类| 题号| 总分 |
| --- | --- | --- |
|---|---|---|
| 复数 | 3（13分） | 13分 |
| 排序 | 5（9分）、6（11分） | 20分 |
| 找规律 | 7（19分） | 19分 |
| 尺取法 | 8（21分） | 21分 |
| DFS/爆破 | 9（23分） | 23分 |
| DP | 4（17分）、10（25分） | 42分 |
可以看到每年蓝桥杯都会考察dfs类型的题，而且分值在23-77分之间不等，虽说分值成逐年下降的趋势，但怎么说也有20+分，蓝桥杯满分150分，普通人（我就是普通人中之一）总共能拿到的分数大概在80分左右，而DFS就包括在这80分之内，所以一定要掌握好。
以上是对题型及分值的分析，接下来分析一下为何蓝桥杯总要考dfs算法？首先看一则人物百科：
再来看一下“深度优先搜索”的百度词条：
还有一点值得提出，这位大神目前好像在中国清北或港大其中一个学校任教。
蓝桥杯作为一个算法类竞赛，再退一步讲，怎么说也得给老前辈一个面子吧。
综上所述，蓝桥杯考dfs算法的概率胜过千足金含金量的比率！
正文
下文的大部分灵感均来自于【】梅森上校《JAVA版本：DFS算法题解两个例子（走迷宫和求排列组合数）》
下面会贴出蓝桥杯第六届B组省赛第3题，第5题；第七届B组省赛第3题，第8题；第八届B组省赛第2题，共5道题。
因为它们都是：凑算式
【第一道题】
【分析】
总共有8个不同的字，每个字都代表不同的数，申请一个一维数组a[8]存储这8个不同的数。
a[8]对应有下标index：0至7
所以dfs方法定义为
public static void dfs(int index)然后设计结束条件，就是index等于8，越界了，代表找够了8个数，尝试进行判断是否构成等式。
if(index == 8) {
int sum = (a[0]*1000+a[1]*100+a[2]*10+a[3]) + (a[4]*1000+a[5]*100+a[6]*10+a[1]);
if(sum == a[4]*10000+a[5]*1000+a[2]*100+a[1]*10+a[7])
System.out.println(a[4]+""+a[5]+""+a[6]+""+a[1]);
return;
}如果index没有越界，a[]数组没存够8个数，就进行搜索。
因为从0至9搜索，且每个数不能重复，所以每访问一个都需要标记一下，visited[i] 为 0 代表未访问，为 1 代表已访问。
for(int i=0; i<=9; i++) {
if(visited[i] == 0) {// 代表没被访问过，可以访问
visited[i] = 1; // 访问 i, 做标记
a[index] = i; // 往数组里放数
dfs(index+1); // 枚举下一种情况
visited[i] = 0; // 回溯, 清除标记
}
}通过数学分析，祥字不可能为0，否则无法进位，三字必为1，因为十进制进位只能进1，所以最终搜索代码如下：
for(int i=0; i<=9; i++) {
if(index == 0 && i == 0) {// 祥字不可能为0，否则就无法进位了
continue;
}
if(index == 4 && i != 1) {// 三字必为1，因为十进制进位只能进1
continue;
}
if(visited[i] == 0) {// 代表没被访问过，可以访问
visited[i] = 1; // 访问 i, 做标记
a[index] = i;
dfs(index+1);
visited[i] = 0; // 回溯, 清除标记
}
}【完整代码】
/** * * 祥瑞生辉
* + 三羊献瑞
* ----------
* 三羊生瑞气
* * 抽象为如下：
* * a[0]a[1]a[2]a[3]
* + a[4]a[5]a[6]a[1]
*-------------------
* a[4]a[5]a[2]a[1]a[7]
* */
public class Main {
static int[] a = new int[8]; // 总共有8个不同的字，代表8个不同的数
static int[] visited = new int[] {0,0,0,0,0,0,0,0,0,0}; // 10个0, 标记0-9十个数是否被访问过
public static void dfs(int index) {
// index为8，越界，代表8个数找够了，同时也是递归结束条件
if(index == 8) {
int sum = (a[0]*1000+a[1]*100+a[2]*10+a[3]) + (a[4]*1000+a[5]*100+a[6]*10+a[1]);
if(sum == a[4]*10000+a[5]*1000+a[2]*100+a[1]*10+a[7])
System.out.println(a[4]+""+a[5]+""+a[6]+""+a[1]);
return;
} else {// 不够8个数，0-9十个数，深搜
for(int i=0; i<=9; i++) {
if(index == 0 && i == 0) {// 祥字不可能为0，否则就无法进位了
continue;
}
if(index == 4 && i != 1) {// 三字必为1，因为十进制进位只能进1
continue;
}
if(visited[i] == 0) {// 代表没被访问过，可以访问
visited[i] = 1; // 访问 i, 做标记
a[index] = i;
dfs(index+1);
visited[i] = 0; // 回溯, 清除标记
}
}
}
}
public static void main(String[] args) {
dfs(0);
}
}没看懂这道题？没关系。继续往下看。
【第二道题】
【分析】
这是一道填空题，基本代码已经给出来了，我只是借题发挥，讲解一下dfs算法。
上一题是8个数，我们设置了一个a[8]，这道题是9个数，所以设置一个a[9]
同样需要一个index：0至8
这道题和上一道题的区别在于题目用了dfs()方法多了一个数组参数，如下
public static void dfs(int[] a, int index)结束条件和上一题类似，当index为9时，越界。
if(index == 9) {
int m = a[0]*1000+a[1]*100+a[2]*10+a[3];
int n = a[4]*10000+a[5]*1000+a[6]*100+a[7]*10+a[8];
if(m*3 == n)
System.out.println(m+" "+n);
return;
}如果index不为9，代表还没凑够9个数，深搜。上一题深搜之前是做标记，深搜之后重置标记，这一题类似，深搜之前交换，深搜之后重置交换，代码如下：
for(int i=index; i<a.length; i++){
int t=a[index]; a[index]=a[i]; a[i]=t; // 交换a[index]和a[i]
dfs(a,index+1);
t=a[index]; a[index]=a[i]; a[i]=t; // 再次交换a[index]和a[i]
}这道填空题需要注意的是，不要完全照抄以致于连 int 都抄上了，导致 t 被声明两次，报错。
【完整代码】
public class Main {
public static void dfs(int[] a, int index) {
// 结束条件
if(index == 9) {
int m = a[0]*1000+a[1]*100+a[2]*10+a[3];
int n = a[4]*10000+a[5]*1000+a[6]*100+a[7]*10+a[8];
if(m*3 == n)
System.out.println(m+" "+n);
return;
}
for(int i=index; i<a.length; i++){
int t=a[index]; a[index]=a[i]; a[i]=t; // 交换a[index]和a[i]
dfs(a,index+1);
t=a[index]; a[index]=a[i]; a[i]=t; // 再次交换a[index]和a[i]
}
}
public static void main(String[] args) {
int[] a = new int[]{1,2,3,4,5,6,7,8,9};
dfs(a,0);
}
}又没看懂？没关系。继续往下看。
【第三道题】
此题和第二道题类似，都是1-9九个数字，不过这里要注意的是，第二题用乘法代替了除法，这道题虽然说也可以改成乘法，但是会相对麻烦一点，干脆就直接用除法，一旦涉及到除法，就有可能产生浮点数，所以我们在声明数组的时候不能再声明为int了，必须声明为double。
index还是int的，取值范围为0至8
dfs方法定义如下：
public static void dfs(double[] a,int index)结束条件就是index==9，越界
if(index == 9) {
if(a[0]+a[1]/a[2]+(a[3]*100+a[4]*10+a[5])/(a[6]*100+a[7]*10+a[8]) == 10)
count++;
return;
}当index不够9的时候，进行深搜
for(int i=index; i<a.length; i++) {
double t = a[index]; a[index]=a[i]; a[i] = t;
dfs(a,index+1);
t = a[index]; a[index]=a[i]; a[i] = t;
}【完整代码】
public class 凑算式交换法dfs {
public static int count = 0;
public static void dfs(double[] a,int index) {
// 结束条件
if(index == 9) {
if(a[0]+a[1]/a[2]+(a[3]*100+a[4]*10+a[5])/(a[6]*100+a[7]*10+a[8]) == 10)
count++;
return;
} else {
for(int i=index; i<a.length; i++) {
double t = a[index]; a[index]=a[i]; a[i] = t;
dfs(a,index+1);
t = a[index]; a[index]=a[i]; a[i] = t;
}
}
}
public static void main(String[] args) {
double[] a = new double[] {1.00,2.00,3.00,4.00,5.00,6.00,7.00,8.00,9.00};
dfs(a,0);
System.out.println(count);
}
}当然，这道题也可以像第一题“三羊献瑞”那样，使用递归之前标记法
【标记法完整代码】
public class 凑算式标记dfs {
public static double[] a = new double[9];
public static int[] visited = new int[] {0,0,0,0,0,0,0,0,0}; // 9个0
public static int count = 0;
public static void dfs(int index) {
// 结束条件
if(index == 9) {
if(a[0]+a[1]/a[2]+(a[3]*100+a[4]*10+a[5])/(a[6]*100+a[7]*10+a[8]) == 10)
count++;
return;
} else {
for(int i=1; i<=9; i++) {
if(visited[i-1] == 0) { // 因为i从1开始，所以需要 -1
visited[i-1] = 1; // 标记
a[index] = (double)i;
dfs(index+1);
visited[i-1] = 0; // 清除标记
}
}
}
}
public static void main(String[] args) {
dfs(0);
System.out.println(count);
}
}对visited初始化的说明：
Java语言int型数组初始化时会自动赋值为0，但是我为了直观表达，所以选择了显式初始化。
今天已经深夜1:22，还有一个四平方和没有写，明天再写
我一定会回来的......
我又回来了，继续看题。
【第四道题】
通过上面的三道题，我想现在的dfs的套路应该已经有一些印象了吧。
因为是四平方，要存四个数，所以我们思考都不用思考，先整个a[4]
同理，需要一个index，0至3
因为前几道题的程序都不需要我们进行输入，这道题需要输入一个num，而且还需要进行等式判断，所以需要作为dfs()方法的一个参数，这样dfs()方法定义如下：
public static void dfs(int index, int num)递归结束条件为index==4，越界，代表a[]数组存够4个数了，可以进行等式判断了，代码如下：
if(index == 4) {
if(num == (int)(Math.pow(a[0], 2)+Math.pow(a[1], 2)
+Math.pow(a[2], 2)+Math.pow(a[3], 2))) {
System.out.println(a[0]+" "+a[1]+" "+a[2]+" "+a[3]);
}
return;
}如果index不等于4，代表4个数还没找够，深搜。这里要注意3件事：
一是深搜的范围，最大范围是三个0和输入数字的开根号。
二是Java中Math.sqrt()方法返回值是double,最好转为int，让两个int进行比较。
三是递归之前要不要留下已访问的标记，或者交换？从给出的输入样例可以看出来，有0 0 1 2 、 0 2 2 2 这样的输出，所以说数字是可以重复使用的，那么就没必要进行标记或者交换了。这也是这道题和前三道题区别之一。
综上，搜索代码如下
for(int i=0; i<=(int)Math.sqrt(num); i++) {
a[index] = i;
dfs(index+1,num);
}【完整代码】
import java.util.Scanner;
public class 四平方和dfs {
public static int[] a = new int[4];
public static void dfs(int index, int num) {
// 结束条件
if(index == 4) {
if(num == (int)(Math.pow(a[0], 2)+Math.pow(a[1], 2)
+Math.pow(a[2], 2)+Math.pow(a[3], 2))) {
System.out.println(a[0]+" "+a[1]+" "+a[2]+" "+a[3]);
}
return;
}
// 搜索
for(int i=0; i<=(int)Math.sqrt(num); i++) {
a[index] = i;
dfs(index+1,num);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
dfs(0,num);
}【等等，这道题还没完】
毕竟是一道23分的大题，尊重一下出题人嘛，怎么会让你这么轻松的拿分呢？
如果按照上面的代码，输入5，会输出下面的结果
5
0 0 1 2
0 0 2 1
0 1 0 2
0 1 2 0
0 2 0 1
0 2 1 0
1 0 0 2
1 0 2 0
1 2 0 0
2 0 0 1
2 0 1 0显然，人家只要第一行。在赵壮同学的指点下，直接在输出下面加一句System.exit(0);就可以了。
System.out.println(a[0]+" "+a[1]+" "+a[2]+" "+a[3]);
System.exit(0); // 加上这句，打印完直接结束程序【再等最后一下，真的】
虽然说上面的代码能够实现输出第一行，但是深搜毕竟是一种盲目的递归，进行大量无用的尝试，最终导致超时。我仅仅是拿这道题让大家更深入了的理解一下dfs这个算法。就上面的代码，我测试了一下 773535 这个输入，Eason的《好久不见》循环播放三遍了都还没跑出来，这要是提交了蓝桥比赛，那就GG了......
其实深搜大部分都可以用for循环暴力破解代替，这样可以减少一下盲目性，比如这道题的解法可以参考下面这篇文章:
【】有梦就不怕痛《蓝桥杯 四平方和》
Java版代码如下（运行飞一般的流畅）：
import java.util.Scanner;
public class 四平方和爆破 {
public static void main(String[] args) {
int n, a, b, c, d;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (a = 0; a < 3000; ++a) {// 3000² = 900万 > 500万
for (b = a; b < 3000; ++b) {
for (c = b; c < 3000; ++c) {
d = (int)Math.sqrt(n - a * a - b * b - c * c);
if (n == a * a + b * b + c * c + d * d) {
if (c > d) {
int temp = d;
d = c;
c = temp;
}
System.out.println(a+" "+b+" "+c+" "+d);
return; // 找到之后就return，让所有循环结束
}
}
}
}
}
}好了，我已经逐个分析了四道题了，本来已经快要分析吐了，不想再分析了。但是后来想了想小王子里面那句话：“每个大人都曾经是个孩子，可又有几个人记得呢？”还有我国晋惠帝说的一句千古名言：“何不食肉糜？”
下面这道题就算是对“凑算式”这类题型的一个总结吧。
【第五道题】
有了上面四道题的经验，看到这种凑算式的题，上来想都不用想：
第一件事，就是设数组
第二件事，数字能否重复使用？能，略过这条；不能，设标记数组，或者交换（我个人偏向设标记数组）
第三件事，定义dfs()方法
第四件事，判断递归结束条件，通常是index越界，并进行等式判断
第五件事，还未凑齐数，深度优先搜索
第六件事，写main()方法
完事
【完整代码】
public class 纸牌三角形dfs {
public static int[] a = new int[9];
public static int[] visited = new int[] {0,0,0,0,0,0,0,0,0};
public static int count = 0;
public static void dfs(int index) {
// 结束条件
if(index == 9) {
if(a[0]+a[1]+a[3]+a[5] == a[0]+a[2]+a[4]+a[8] &&
a[0]+a[1]+a[3]+a[5] == a[5]+a[6]+a[7]+a[8]) {
count++;
}
return;
}
// 搜索
for(int i=1; i<=9; i++) {
if(visited[i-1] == 0) { // i从1开始，所以要i-1
visited[i-1] = 1;
a[index] = i;
dfs(index+1);
visited[i-1] = 0;
}
}
}
public static void main(String[] args) {
dfs(0);
System.out.println(count/6);
}
}这道题有个坑就是要去重，因为题中说明“旋转，镜像后相同的算一种”，所以最后要count/6.这个纯靠经验了，有过旋转经验的就知道，每个数都有机会占在顶点上，所有数固定后，转动的话，等于每个数计算了3次，所以要除以3；对于镜像，同样是靠经验，如果你知道从镜子里看左右会对换的话，就会知道要除以2，总共除以6.
在没做这道题之前，我是不知道镜像是什么样的，因此我还特意拿个镜子照了照。
这篇文章就到此结束吧，我要开一个新坑了，明天应该能发布新文章：
如果看完这5道题还不会这种“凑算式”的题，请发QQ邮箱：424171723@qq.com 或 直接加我QQ，进行手把手教学。
【参考文章】
- 【】梅森上校《JAVA版本：DFS算法题解两个例子（走迷宫和求排列组合数）》
- 【】winycg《2015蓝桥杯 三羊献瑞（回溯法dfs）》
- 【】有梦就不怕痛《蓝桥杯 四平方和》
- 还有一些、博客园、简书.......由于浏览篇幅太多，所以一些未列在其中，表示抱歉