剪邮票

如【图1.jpg】,

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

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

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

 思路 ： 枚举格子，BFS判断连通。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int   mp[4][5];
int   num[7];
int   dir[4][2] ={ {0,1},{0,-1},{-1,0},{1,0}};
int   vis[4][5];
struct Node{
	   int x,y;
}node;

int    changexy( int n ){
	   for( int i=1;i<=3;i++){
	   	    for( int j=1;j<=4;j++){
	   	    	 if( mp[i][j] == n )
	   	    	     return i;
			   }
	   }
}
bool  change( ){
	  memset(vis,0,sizeof(vis));
	  int x,y;
	  for( int i=1;i<=5;i++){
	       x = changexy( num[i] );
		   y = num[i] - (x-1)*4;
		   vis[x][y] = 1 ; 
	  }
        
	  node.x=x;
	  node.y=y;
	  queue< struct Node > q;
	  q.push( node );
	  vis[x][y] =  0; 
	  while( !q.empty() ){
	  	   node = q.front();
	  	   q.pop();
	  	   x = node.x;
	  	   y = node.y; 
		   for( int i=0;i<=3;i++){
	  	   	    node.x = x + dir[i][0];
				node.y = y + dir[i][1]; 
				 
			    if( node.x>=1 && node.x<=3 && node.y>=1&&node.y<=4 && vis[node.x][node.y]){
	  	            vis[node.x][node.y] = 0; 
			   	    q.push(node); 
			  } 	    
			 } 
	  } 
	 
	  for( int i=1;i<=3;i++){
	  	   for( int j=1;j<=4;j++){
	  	   	    if( vis[i][j] ==1)
	  	   	        return false;
			 }
	  }        	  
	  return true;
}
int   main(void){
	  
	  int cnt=0;
	  for( int i=1;i<=3;i++){
	  	 for( int j=1;j<=4;j++){
	  	 	  mp[i][j]=++cnt;
		   }
	  }
	  int ans=0;
	  for(  num[1]=1;num[1]<=8;num[1]++){
	  	  
	  for(  num[2]=num[1]+1;num[2]<=9;num[2]++){
	  
	  for(  num[3]=num[2]+1;num[3]<=10;num[3]++){
	  
	  for(  num[4]=num[3]+1;num[4]<=11;num[4]++){
	  
	  for(  num[5]=num[4]+1;num[5]<=12;num[5]++){
	  	    if( change() )
	  	        ans++;  
	  }	
	  }	
	  }	
	  } 
	  }
    printf("%d\n",ans);
   	return 0;
}