剪邮票

/*如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。

（仅仅连接一个角不算相连）

比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

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

请填写表示方案数目的整数。

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

*/
package test;

import java.util.HashSet;

public class 剪邮票 {
    static int[] a=new int[5];
    static HashSet<String> hashset=new HashSet<String>();//只能存放不同的元素
    public static void main(String[] args) {
        for(a[0]=0;a[0]<12;a[0]++){
            for(a[1]=a[0]+1;a[1]<12;a[1]++){
                for(a[2]=a[1]+1;a[2]<12;a[2]++){
                    for(a[3]=a[2]+1;a[3]<12;a[3]++){
                        for(a[4]=a[3]+1;a[4]<12;a[4]++){
                            if(check())
                                hashset.add(""+a[0]+a[1]+a[2]+a[3]+a[4]);
                        }
                    }
                }
            }
        }
        System.out.print(hashset.size());
    }
    
    public static boolean check(){//检查五张邮票是否相连
        boolean[] flag=new boolean[5];
        dfs(flag,0);
        return flag[0]&&flag[1]&&flag[2]&&flag[3]&&flag[4];
    }

    public static void dfs(boolean[] flag,int n) {//遍历得出5个数的相邻关系，n可为所有的数且i也可为所有的数，
        flag[n]=true;
        for(int i=0;i<5;i++){
            if(!flag[i]&&(a[i]/4==a[n]/4)&&(a[i]==a[n]-1||a[i]==a[n]+1))//当i个数没有遍历过，且两个数在同一行且相邻，则遍历该数，将i该数附为true
                dfs(flag,i);
            if(!flag[i]&&(a[i]%4==a[n]%4)&&(a[i]==a[n]-4||a[i]==a[n]+4))//两个数在同一列且相邻
                dfs(flag,i);
        }
    }
}