剪邮票 蓝桥杯

剪邮票

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

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

思路：先用枚举举出所有的例子，然后再使用bfs判定联通，不使用dfs的原因是dfs得到的是一笔画成的图形，有的图形不能够判断。

#include<bits/stdc++.h>
using namespace std;
int vis[3][4];
int ans =0;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct zuobiao{
	int x,y;

}num[5];
void  init_zuobiao(zuobiao &z,int n)
{
	if(n==4||n==8||n==12)
		z.x= n/4-1;
	else	z.x=n/4;
		z.y= (n-1)%4;
		return ;
}
int bfs (zuobiao *num)
{
	queue <zuobiao> q;
   zuobiao s;
   s.x=num[0].x;
   s.y=num[0].y;
   vis[s.x][s.y]=0;
	q.push(s);
	zuobiao m,t;
	int k=1;
	while(!q.empty())
	{
		t= q.front();
		q.pop();
		for(int i=0;i<4;i++){
			m.x = t.x+dir[i][0];
			m.y = t.y+dir[i][1];
			if(m.x>=0&&m.y>=0&&m.x<=2&&m.y<=3&&vis[m.x][m.y]==1){
				k++;
				vis[m.x][m.y]=0;
				q.push(m);
			}
		}
	}
	return k;
}
int main()
{
	
	int a,b,c,d,e;
	for(a = 1;a<=12;a++)
	 for(b=a+1;b<=12;b++)
	  for(c=b+1;c<=12;c++)
	   for(d=c+1;d<=12;d++)
	    for(e=d+1;e<=12;e++)
	     {
	     	memset(vis,0,sizeof(vis));
	        init_zuobiao(num[0],a);
	        vis[num[0].x][num[0].y]=1;
			init_zuobiao(num[1],b);
		     vis[num[1].x][num[1].y]=1;
			init_zuobiao(num[2],c);
			 vis[num[2].x][num[2].y]=1;
			init_zuobiao(num[3],d);
			 vis[num[3].x][num[3].y]=1;
			init_zuobiao(num[4],e);  
			 vis[num[4].x][num[4].y]=1;
			 if(bfs(num)==5)	{
			 	ans++;
			 }
	     }
	     cout<<ans;
	     return 0;
}