蓝桥杯-剪邮票

刺骨的言语ヽ痛彻心扉 2022-06-18 10:16 168阅读 0赞

剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。  
现在你要从中剪下5张来，要求必须是连着的。  
（仅仅连接一个角不算相连）  
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。  
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

## 图的深度优先搜索：巧妙的暴力+深优探测面积。用一维数组存储，同行加减一，同列加减四。必须很快想清思路，再很快搭建，打断点调试 ##

![这里写图片描述][SouthEast]

package lastReal;
    
    public class myCutStamps {
        static int[] a={
       0,0,0,0,0};
        static int[] b=new int[12];
        static int[] bb=new int[12];
        static int[] n={
       1,-1,4,-4};
        static int sum=0,cnt=0;
        public static void main(String[] args) {
            for(a[0]=0;a[0]<=11;a[0]++)
                for(a[1]=a[0]+1;a[1]<=11;a[1]++)
                    for(a[2]=a[1]+1;a[2]<=11;a[2]++)
                        for(a[3]=a[2]+1;a[3]<=11;a[3]++)
                            for(a[4]=a[3]+1;a[4]<=11;a[4]++){
                                for(int i=0;i<=11;i++){
                                    bb[i]=0;
                                    b[i]=0;
                                }
                                for(int i=0;i<=4;i++){
                                b[a[i]]=1;
                                }
                                sum=0;
                                f(a[0]);
                            }
            System.out.println(cnt);
        }
        static void f(int k){
            int kk=0;
            if(sum==5){
                cnt++;
                System.out.println(a[0]+""+a[1]+a[2]+a[3]+a[4]);
                return;
            }
            for(int i=0;i<=3;i++){
                if((i==0||i==1)&&(k+n[i])/4==k/4){
                    kk=k+n[i];
                }else if (i==2||i==3) {
                    kk=k+n[i];
                }else{
                    continue;
                }
                if(kk<0||kk>11) {
                    continue;
                }
                if(bb[kk]==0&&b[kk]==1){
                    bb[kk]=1;
                    sum++;
                    f(kk);
                }
            }
        }
    
    }

[SouthEast]: /images/20220618/1c9335801178428fba090d5e679768df.png