剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：深搜找到 12 个数中 5个数的组合，然后使用广度优先搜索判断选出的5个是否联通。
错误思路 1：使用直接使用深度搜索，由于深度搜索过程中不会转弯以下的情况搜索不到
图片来自 ：https://blog.csdn.net/eventqueue/article/details/50954641
2：不使用bfs判断联通，而是直接判断 上下左右是否有联通的点，以下情况错误
1 1 1 0
0 0 0 0
0 1 1 0
代码：
public class Stamp {
public static int num = 0;
public static int[] vis = new int[5];
public static int[][] next = {{0,1},{1,0},{0,-1},{-1,0}};
public static int[][] stamp = new int[3][4];
public static int[] visit = new int[12];
public static int[] have = new int[5];
///
public static void main(String[] args) {
dfs(0,0);
System.out.println(num);
}
///select five visiable number
public static void dfs(int step,int i){
if(step >= 5){
if(bfs()){
num++;
}
return;
}
for(;i<12;i++){
if(visit[i] == 0){
visit[i] = 1;
have[step] = i;
stamp[i/4][i%4] = 1;
dfs(step+1,i+1);
stamp[i/4][i%4] = 0;
visit[i] = 0;
}
}
}
///justify if accessable
public static boolean bfs(){
Queue<Integer> q = new LinkedList<Integer>();
q.offer(have[0]);
stamp[have[0]/4][have[0]%4] = -1;
int step = 1;
while(q.peek()!=null){
int e = q.poll();
for(int j=0;j<4;j++){
int ni = e/4+next[j][0];
int nj = e%4+next[j][1];
if(ni<3 && ni>-1 && nj<4 && nj>-1 && stamp[ni][nj] == 1){
stamp[ni][nj] = -1;
step++;
q.offer(ni*4+nj);
}
}
}
/// offset
for(int i=0;i<5;i++){
int h = have[i];
stamp[h/4][h%4] = 1;
}
return step == 5;
}
///exit
/*
1 1 1 0 0
0 0 0 0 0
0 1 1 0 0
*/
///don't work
public static boolean justify(){
//search first node
boolean flag = false;
for(int i=0;i<5;i++){
// up down left right
for(int j=0;j<4;j++){
int ni = have[i]/4+next[j][0];
int nj = have[i]%4+next[j][1];
if(ni<3 && ni>-1 && nj<4 && nj>-1 && stamp[ni][nj] == 1){
flag = true;
break;
}
}
if(!flag){
return false;
}
else{
flag = false;
}
}
return true;
}
}