剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
-------------------------------------------------------------------------------------------------
思路：1.五重循环求出找出所有可能的邮票减法，注意去掉剪的邮票相同但剪的次序不同的情况。2.dfs每种剪法。利用{+4,-4,+1,-1}的位置关系来判断每张邮票是否是上下左右相邻的，此时要注意4+1=5的情况。
public class Main {
static int way[] = {-4,-1,1,4};
static int sum = 0;
public static void main(String args[]){
int flag[] = new int[13];
for(int a = 1;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++){
if(a!=b&&a!=c&&a!=d&&a!=e&&
b!=c&&b!=d&&b!=e&&
c!=d&&c!=e&&
d!=e){
// 得到所有可能的剪法
int arrays[] = {a,b,c,d,e};
flag[a] = 1;
flag = new int[13];
qiu(arrays[0],flag,arrays);
int l;
for(l = 0;l<=4;l++){
if(flag[arrays[l]]==0){
break;
}
}
if(l==5){
sum++;
}
}
}
}
}
}
}
System.out.println(sum);
}
// dfs
public static void qiu(int goal,int flag[],int arrays[]){
int i;
int res = 0;
for(i = 0;i<4;i++){
res = goal+way[i];
int mark = com(arrays,res);
if(mark == 1 && flag[res] == 0){
if(res == 5&&goal==4) {
continue;
}
if(res == 9&&goal==8) {
continue;
}
if(res == 4&&goal==5) {
continue;
}
if(res == 8&&goal==9) {
continue;
}
flag[res] = 1;
qiu(res,flag,arrays);
}
}
}
public static int com(int arrays[],int temp){
for(int i = 0;i<arrays.length;i++){
if(arrays[i] == temp){
return 1;
}
}
return -1;
}
}
