第七题：
剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
从这道题开始蓝桥杯的题目就开始增加难度了，这道题首先第一眼要有DFS算法的感觉，第二点要知道DFS算法的局限性，DFS算法是一直搜索下去无法走回头路的，即所谓的“一笔画”特点。我们观察样例的第二个图发现，这个图形是不能“一笔画”的，所以DFS在这里是无法用来判别连通性的。
因此，想法一：把每一个邮票进行DFS搜索然后除以5来得到正确结果是不可能的！
我们来看一下想法二：用DFS进行深搜，而用BFS来进行宽搜。
首先BFS算法是可以走回头路的，因此我们用BFS来进行联通块的块数判别，如果BFS判别块数为5，则方法+1；
/*
name:Rollchuchy
type:
*/
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int ans=0;
int det=0;
int map[3][4];
int vis[3][4];
int dis[4][2]={
0,1,
0,-1,
1,0,
-1,0
};
struct node{
int x,y;
node(){}
node(int x,int y):x(x),y(y){}
}a[10];
void init()
{
/*int num=1;
for(int i=0;i<3;i++){
for(int j=0;j<4;j++){
map[i][j]=num;
num++;
}
}*/
for(int i=0;i<3;i++){
for(int j=0;j<4;j++){
vis[i][j]=0;
}
}
}
int bfs()
{
int num;
memcpy(map,vis,sizeof(map));
queue<node> que;
que.push(a[0]);
map[a[0].x][a[0].y]=0;
num=1;
while(!que.empty())
{
node start=que.front();que.pop();
for(int i=0;i<4;i++){
int xx=start.x+dis[i][0];
int yy=start.y+dis[i][1];
if(xx>=0&&xx<3&&yy>=0&&yy<4&&map[xx][yy])
{
map[xx][yy]=0;
num++;
que.push(node(xx,yy));
}
}
}
return num;
}
void dfs(int row,int col,int len){
if(len==5){
if(bfs()==5)
ans++;
return ;
}
if(row>=3)return ;
for(int i=col;i<=4;i++){
if(i<4){
vis[row][i]=1;
a[det]=node(row,i);
det++;
dfs(row,i+1,len+1);
det--;
vis[row][i]=0;
}
else {
dfs(row+1,0,len);
}
}
}
int main()
{
init();
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
