首页 > 代码库 > 蓝桥杯比赛关于 BFS 算法总结方法以及套路分析
蓝桥杯比赛关于 BFS 算法总结方法以及套路分析
首先我们来看两道java A组的题目，都是同一年的哦！！！
搭积木
小明最近喜欢搭数字积木，
一共有10块积木，每个积木上有一个数字，0~9。
搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。
下面是两种合格的搭法：
0
1 2
3 4 5
6 7 8 9
0
3 1
7 5 2
9 8 6 4
请你计算这样的搭法一共有多少种？
请填表示总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
先帖代码：
public class test4 {
int a[]=new int[20]; //java 数组初始化值为0
int visit[]=new int[20]; //判断是否使用过
static int count1=0;
public void dfs1(int x){
if(x==10){
if(a[0]<a[1]&&a[0]<a[2] //这里没有进行剪枝操作，因为不方便
&&a[1]<a[3]&&a[1]<a[4]&&a[2]<a[4]&&a[2]<a[5]
&&a[3]<a[6]&&a[3]<a[7]&&a[4]<a[7]&&a[4]<a[8]&&a[5]<a[8]&&a[5]<a[9]){
count1++;
return;
}
}
for(int i=0;i<10;i++){
if(visit[i]==0){ //深度搜索套路代码，只可意会
a[x]=i;
visit[i]=1;
dfs1(x+1);
visit[i]=0;
}
}
return; //这个return是当前面的所有的都不成立时回溯(return)到最初调用for循环内的dfs处
}
public static void main(String[] args){
new test4().dfs1(0);
System.out.println(count1);
}
}
结果：768
题目二：
寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来，可以参见【图1.jpg】)
每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）
你一共找到了多少种方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
代码：
public class test3 {
int a[]=new int[20]; //java 数组初始化值为0
int visit[]=new int[20];
static int count=0;
public void dfs(int x){ //相当于剪枝操作
/*if(x>3&&a[1]+a[2]!=a[3]) //如果前三个数已经被取出来但不符合题设条件，则返回重找
return;
if(x>6&&a[4]-a[5]!=a[6]) //若前三个数满足第一条，看4-6个数是否满足第二个条件
return;
if(x>9&&a[7]*a[8]!=a[9]) //同上
return;
if(x>12&&a[12]*a[11]==a[10]) //如果所有条件均满足，则让count++
{
count++;
return;
}*/
if(x>12){
if((a[1]+a[2]==a[3])&&(a[4]-a[5]==a[6])&&(a[7]*a[8]==a[9])&&(a[12]*a[11]==a[10])){
count++;
return;
}
}
for(int i=1;i<14;i++){
if(visit[i]==0){ //深度搜索套路代码
a[x]=i;
visit[i]=1;
dfs(x+1);
visit[i]=0;
}
}
return; //这个return是当前面的所有的都不成立时回溯(return)到最初调用for循环内的dfs处
}
public static void main(String[] args){
new test3().dfs(1);
System.out.println(count);
}
}
结果： 64
蓝桥杯比赛关于 BFS 算法总结方法以及套路分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。