题目来源：第七届蓝桥杯省赛c/c++ b组 第七题

剪邮票

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

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

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

解题思路 

用组合数遍历所有情况，然后在选出满足条件的
怎么判断是否相连了，用并查集，如果这5张邮票在同一个连通块，那么就满足条件

#include<iostream>
#include<cmath>
using namespace std;
class Node{public: int row;int col;Node(int r=0,int c=0){row=r;col=c;}
};int isSelected[12];//是否被选 
int fa[5];//五张邮票 
Node x[5];
Node zb[12]={Node(0,0),Node(0,1),Node(0,2),Node(0,3),Node(1,0),Node(1,1),Node(1,2),Node(1,3),Node(2,0),Node(2,1),Node(2,2),Node(2,3)};
int ans;int find(int x)
{int r = x;while (fa[r] != r)//查找根节点(找到老大是谁){		 r = fa[r];}//压缩int i = x, j;while (fa[i] != r){j = fa[i];//保存上一个结点fa[i] = r;//压缩当前结点i = j;//准备压缩上一个结点}return r;
}
void mix(int x, int y)//让y成为x的直接老大 
{int fx = find(x), fy = find(y); fa[fx] = fy;
}bool isXL(Node x,Node y){//判断两张是否相邻 if( (abs(x.row-y.row)==0&&abs(x.col-y.col)==1)||(abs(x.row-y.row)==1&&abs(x.col-y.col)==0) )return true;else return false;	
}
bool judge(){for(int i=0;i<5;i++)fa[i]=i;int k=0;//将选的五张邮票放到x中 for(int i=0;i<12;i++)if(isSelected[i])x[k++]=zb[i];for(int i=0;i<4;i++)for(int j=i+1;j<5;j++){if(isXL(x[i],x[j]))mix(i,j);} for(int i=0;i<4;i++){if(find(i)!=find(i+1))return false;	}return true;		
}
void print_yp(){printf("Case%d:\n",ans);for(int i=0;i<12;i++){if(isSelected[i])printf("  *");else printf("%3d",i+1);if((i+1)%4==0)printf("\n");}
}
void dfs(int n,int m){//12张，每张都可以选择或不选择 时间复杂度O(2^12) if(n==0){if(m==0){if(judge()){//选出的5张满足条件ans++; print_yp();		 		}			}return;}isSelected[n-1]=0;dfs(n-1,m);//第n张不选,接下来从n-1张里选m张 isSelected[n-1]=1;		dfs(n-1,m-1);//第n张选,接下来从n-1张里选m-1张 		
}
void solve(){for(int i=0;i<12;i++)isSelected[i]=0;ans=0;dfs(12,5);	printf("%d\n",ans);
}
int main(){solve();		return 0;
}