剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：
刚开始想的是dfs,一天之后才发现不行，因为dfs只能向一个方向搜索，有些状态搜索不到。比如下面的情况
当然BFS也不行。
先选5个数，换算坐标之后判断五个是否相连，队友用的是并查集，我用了dfs，最后结果116
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
struct node {
int x,y;
} ans[5];
int bns[5],sum=0,Map[3][4],cnt,dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
void dfs(node a) {
for(int i=0; i<=3; i++) {
int xx=a.x+dir[i][0],yy=a.y+dir[i][1];
for(int j=0; j<=4; j++) {
if(xx<0||xx>2||yy<0||yy>3)continue;
if(xx==ans[j].x&&yy==ans[j].y&&Map[ans[j].x][ans[j].y]==0) {
cnt++;Map[ans[j].x][ans[j].y]=1;
if(cnt==5)return;
else {
node temp=ans[j];dfs(temp);
}
}
}
}
}
void check() {
sort(bns,bns+5);memset(Map,0,sizeof(Map));cnt=1;
for(int i=0; i<=4; i++) {
ans[i].x=bns[i]/4;ans[i].y=bns[i]%4;
}
Map[ans[0].x][ans[0].y]=1;
node temp=ans[0];
dfs(temp);
if(cnt==5)sum++;
}
int main() {
for(int i=0; i<=7; i++)
for(int j=i+1; j<=8; j++)
for(int k=j+1; k<=9; k++)
for(int p=k+1; p<=10; p++)
for(int q=p+1; q<=11; q++) {
bns[0]=i;bns[1]=j;bns[2]=k;bns[3]=p;bns[4]=q;
check();
}
printf("%d",sum);
return 0;
}