剪邮票
这是本人第一次写博客，希望大家多多支持！ 如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
答案：116
思路：本来一开始准备用全排列做的，结果发现严重超时，转而思考dfs，也就是用最标准的dfs模板，但是要注意的一个点是边界的处理，所以我们把1到12换成了1,2,3,4,6,7,8,9,11,12,13,14,便于处理，上代码：
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int num[20]; int vis[20]; int temp[]={1,2,3,4,6,7,8,9,11,12,13,14};//这一步至关重要 int step[4]={-5,-1,1,5}; int ans; void dfs(int index) { if(index==5){ int flag1=1; int flag2=0; for(int i=0;i<5;i++){ if(vis[num[i]-1]==0&&vis[num[i]+1]==0&&vis[num[i]-5]==0&&vis[num[i]+5]==0){ flag1=0; } } int count=0; for(int i=0;i<5;i++){ for(int j=0;j<4;j++){ if(vis[num[i]-step[j]]==1){ count+=1; } } } if(count>6){ flag2=1; } if(flag1==1&&flag2==1){ ans+=1; } return; } for(int i=0;i<12;i++){ if(vis[temp[i]]==0){ num[index]=temp[i]; vis[temp[i]]=1; dfs(index+1); vis[temp[i]]=0; } } } int main(){ ans=0; memset(vis,0,sizeof(vis)); dfs(0); cout << ans/120 << endl; return 0; }如有错误，欢迎批评指正！
