/*如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。 请你计算，一共有多少种不同的剪取方法。 请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。*/

 

 

 

 

 

方法一：排列组合 （深度优先）

     1、12个数字中选中5个 

     2、深度遍历5个数字是否相邻

import java.util.*;public class Main{    static int[] num;    static boolean[] vis;    static boolean judge() {        vis = new boolean[6];        dfs(1);        return vis[1]&&vis[2]&&vis[3]&&vis[4]&&vis[5];    }        static void dfs(int x) {        vis[x] = true;        for(int i=1;i<=5;i++) {            if(!vis[i]&&(num[i]/4==num[x]/4)&&(num[i]==num[x]-1||num[i]==num[x]+1))//数num[i]没有遍历过，且两个数在同一行且相邻，则遍历该数，将i该数附为true                dfs(i);            if(!vis[i]&&(num[i]%4==num[x]%4)&&(num[i]==num[x]-4||num[i]==num[x]+4))//两个数在同一列且相邻                dfs(i);        }    }    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        num = new int[15];        int cnt = 0;                for(num[1]=0;num[1]<12;num[1]++)    //0-11            for(num[2]=num[1]+1;num[2]<12;num[2]++)                for(num[3]=num[2]+1;num[3]<12;num[3]++)                    for(num[4]=num[3]+1;num[4]<12;num[4]++)                        for(num[5]=num[4]+1;num[5]<12;num[5]++) {                            if(judge()) cnt++;                        }        System.out.println(cnt);    }}

方法二  排列组合

    1、个数字中选中5个 

     2、广度优先遍历5个数字是否相邻

public class JAVA7{        static boolean[] vis;        public static void main(String[] args) {                Scanner scanner = new Scanner(System.in);        int[] num = {1,2,3,4,6,7,8,9,11,12,13,14};                int cnt = 0;                for(int a=0;a<12;a++)            for(int b=a+1;b<12;b++)                for(int c=b+1;c<12;c++)                    for(int d=c+1;d<12;d++)                        for(int e=d+1;e<12;e++) {                            vis = new boolean[15];                            vis[num[a]] = true;                            vis[num[b]] = true;                            vis[num[c]] = true;                            vis[num[d]] = true;                            vis[num[e]] = true;                                                        Queue
     
       queue = new LinkedList<>();                            queue.add(num[a]);                            vis[num[a]] = false;                            int num1 =0;                                                        while(!queue.isEmpty()) {                                int top = queue.poll();                                num1++;                                if(top+5<15&&top+5>=0&&vis[top+5]) {queue.add(top+5); vis[top+5]=false;}                                if(top-5>=0&&top-5<15&&vis[top-5]) {queue.add(top-5); vis[top-5]=false;}                                if(top+1<15&&top+1>=0&&vis[top+1]) {queue.add(top+1); vis[top+1]=false;}                                if(top-1>=0&&top-1<15&&vis[top-1]) {queue.add(top-1); vis[top-1]=false;}                                                            }                            if(num1==5) cnt++;                        }        System.out.println(cnt);    }}