搭积木+寒假作业+方格填数 DFS解法

朴灿烈づ我的快乐病毒、 2022-04-11 04:44 189阅读 0赞

## [蓝桥杯比赛关于 DFS 算法总结方法以及套路分析][DFS] ##

首先我们来看几道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

> 第三题：
> 
>   
> 方格填数
> 
> 如下的10个格子  
>    +--+--+--+  
>    |0 | 1| 2|  
> \+--+--+--+--+  
> | 3| 4| 5| 6|  
> \+--+--+--+--+  
> | 7| 8| 9|  
> \+--+--+--+
> 
> （如果显示有问题，也可以参看【图1.jpg】）
> 
> 填入0~9的数字。要求：连续的两个数字不能相邻。  
> （左右、上下、对角都算相邻）
> 
> 一共有多少种可能的填数方案？
> 
> 请填写表示方案数目的整数。  
> 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

public class test5 {
     
        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(
                           (Math.abs(a[0]-a[1])!=1)&&
                           (Math.abs(a[0]-a[3])!=1)&&
                           (Math.abs(a[0]-a[4])!=1)&&
                           (Math.abs(a[0]-a[5])!=1)&&
                           (Math.abs(a[1]-a[2])!=1)&&
                           (Math.abs(a[1]-a[4])!=1)&&
                           (Math.abs(a[1]-a[5])!=1)&&
                           (Math.abs(a[1]-a[6])!=1)&&
                           (Math.abs(a[2]-a[5])!=1)&&
                           (Math.abs(a[2]-a[6])!=1)&&
                           (Math.abs(a[3]-a[0])!=1)&&
                           (Math.abs(a[3]-a[4])!=1)&&
                           (Math.abs(a[3]-a[7])!=1)&&
                           (Math.abs(a[3]-a[8])!=1)&&
                           (Math.abs(a[4]-a[5])!=1)&&
                           (Math.abs(a[4]-a[7])!=1)&&
                           (Math.abs(a[4]-a[8])!=1)&&
                           (Math.abs(a[4]-a[9])!=1)&&
                           (Math.abs(a[5]-a[6])!=1)&&
                           (Math.abs(a[5]-a[8])!=1)&&
                           (Math.abs(a[5]-a[9])!=1)&&
                           (Math.abs(a[6]-a[9])!=1)&&
                           (Math.abs(a[7]-a[8])!=1)&&
                           (Math.abs(a[8]-a[9])!=1)
                           ){
                       count1++;
                        return;
                   }
        /*         if(a[0]!=a[1]&&a[0]!=a[3]&&a[0]!=a[4]&&a[0]!=a[5]
                           &&a[1]!=a[0]&&a[1]!=a[2]&&a[1]!=a[4]&&a[1]!=a[5]&&a[1]!=a[6]
                                   &&a[2]!=a[1]&&a[2]!=a[5]&&a[2]!=a[6]
                                           &&a[3]!=a[0]&&a[3]!=a[0]&&a[3]!=a[7]
                                                   &&a[4]!=a[0]&&a[4]!=a[1]&&a[4]!=a[3]&&a[4]!=a[5]&&a[4]!=a[7]&&a[4]!=a[8]&&a[4]!=a[9]
                                                           &&a[5]!=a[0]&&a[5]!=a[1]&&a[5]!=a[2]&&a[5]!=a[4]&&a[5]!=a[6]&&a[5]!=a[8]&&a[5]!=a[9]
                                                                   &&a[6]!=a[1]&&a[6]!=a[2]&&a[6]!=a[5]&&a[6]!=a[9]
                                                                           &&a[7]!=a[3]&&a[7]!=a[4]&&a[7]!=a[8]
                                                                                   &&a[8]!=a[3]&&a[8]!=a[4]&&a[8]!=a[5]&&a[8]!=a[7]&&a[8]!=a[9]
                                                                                           &&a[9]!=a[4]&&a[9]!=a[5]&&a[9]!=a[6]&&a[9]!=a[8]){
                    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 test5().dfs1(0);
               System.out.println(count1);
           }
         
    }

执行结果：  1580

[DFS]: https://www.cnblogs.com/liushuncheng/p/6629514.html