2016年第七届蓝桥杯CC++程序设计本科B组省赛 剪邮票(结果填空)

剪邮票

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

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

//枚举5个点，然后dfs判断联通性 #include<cstdio> #include<iostream> #include<cstring> using namespace std; int cnt,dir[5]={-4,1,-1,4},i1,i2,i3,i4,i5,vis[20]; void dfs(int i){ if(cnt<5) for(int j=0;j<4;j++) { if((i==4||i==8)&&dir[j]==1) continue;//这个一开始忘了 if((i==5||i==9)&&dir[j]==-1) continue; int t=i+dir[j]; if(cnt<5&&t>0&&t<13&&!vis[t]&&(t==i2||t==i3||t==i4||t==i5)) { vis[t]=1; cnt++; dfs(t); } } } int main(){ int ans=0; for(i1=1;i1<=12-4;i1++) for(i2=i1+1;i2<=12-3;i2++) for(i3=i2+1;i3<=12-2;i3++) for(i4=i3+1;i4<=12-1;i4++) for(i5=i4+1;i5<=12;i5++) { memset(vis,0,sizeof(vis)); cnt=1; dfs(i1); if(cnt==5) ans++; } cout<<ans<<endl; return 0; } //结果：116