【算法】蓝桥杯dfs深度优先搜索之凑算式总结

本文               → 《【算法】蓝桥杯dfs深度优先搜索之凑算式总结》

相关文章        →《【算法】蓝桥杯dfs深度优先搜索之排列组合总结》

                      →《【算法】蓝桥杯dfs深度优先搜索之图连通总结》

 

前言

曾几何时这个词现在用正适合不过了。

曾几何时我还是对dfs算法一脸懵x的状态，虽说大二的时候学过数据结构，但是那一学期被我荒废了......详情等我毕业了再说吧。

还有四天就要考蓝桥杯了，我分析了近四年的蓝桥杯（B组）题型，分类纯属个人理解，并非官方宣布，如下表：

注：

以下DFS代表Depth First Search首字母缩写，即深度优先搜索，简称深搜

以下DP代表Dynamic Programming首字母缩写，即动态规划，没有简称 : )

 

2015年（第六届）蓝桥杯B组省赛

分类	题号	总分
水题	1（3分）、2（5分）、4（11分）	19分
DFS/爆破	3（9分）、5（15分）、7（21分）	45分
冒泡 （加法乘法）	6（17分）	17分
取余 （饮料换购）	8（13分）	13分
矩阵	9（25分）	25分
DP	10（31分）	31分

2016年（第七届）蓝桥杯B组省赛

分类	题号	总分
递推	1（3分）、2（5分）	8分
函数调用	4（11分）	11分
DFS/爆破	3（9分）、5（13分）、 6（15分）、7（19分）、 8（21分）	77分
DP	9（23分）	23分
数据结构	10（31分）	31分

2017年（第八届）蓝桥杯B组省赛

分类	题号	总分
文件处理	1（5分）、3（13分）	18分
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组省赛

分类	题号	总分
水题	1（5分）、2（7分）	12分
复数	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算法的概率胜过千足金含金量的比率！

---

正文

下文的大部分灵感均来自于【CSDN】梅森上校《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循环暴力破解代替，这样可以减少一下盲目性，比如这道题的解法可以参考下面这篇文章:

【CSDN】有梦就不怕痛《蓝桥杯 四平方和》

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.

在没做这道题之前，我是不知道镜像是什么样的，因此我还特意拿个镜子照了照。

 

 

 

这篇文章就到此结束吧，我要开一个新坑了，明天应该能发布新文章：

《【算法】蓝桥杯dfs深度优先搜索之排列组合总结》

 

如果看完这5道题还不会这种“凑算式”的题，请发QQ邮箱：424171723@qq.com 或 直接加我QQ，进行手把手教学。

 

---

【参考文章】

1. 【CSDN】梅森上校《JAVA版本：DFS算法题解两个例子（走迷宫和求排列组合数）》
2. 【CSDN】winycg《2015蓝桥杯 三羊献瑞（回溯法dfs）》
3. 【CSDN】有梦就不怕痛《蓝桥杯 四平方和》
4. 还有一些CSDN、博客园、简书.......由于浏览篇幅太多，所以一些未列在其中，表示抱歉