有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连） 请你计算，一共有多少种不同的剪取方法。
其实一开始看这题的时候我理所当然的认为这题用dfs搜的完事了，写好代码往上就往上提交了，然后就错了 然后我就发现事情没那么简单，因为邮票的图形可以是这样的 这样用搜索可搜不出来，所以我转变思路，可以先找出5个小邮票，如果能拼成一个大的邮票，则答案加1.于是代码就出来了，其他说明我都放在代码上了(
#include <iostream> #include <cstring> using namespace std; int g[3][4],cnt,ans,num[5],vis[3][4]; const int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}}; void dfs(int x,int y) { vis[x][y]=1;//确保不会被重复搜索 cnt++;//cnt=5了就代表5个小邮票可以连成一片 for(int i=0; i<4; i++) { int dx=x+dir[i][0]; int dy=y+dir[i][1]; if(dx<3 && dy<4 && dx>=0 && dy>=0 && vis[dx][dy]==0 &&g[dx][dy]==1) { dfs(dx,dy); } } } void solve(int step,int k) { if(step == 5) {//凑够5个数了就把他存到图 int x,y; for(int i=0; i<5; i++) { x=(num[i]-1)/4; y=(num[i]-1)%4; g[x][y]=1; } dfs((num[0]-1)/4,(num[0]-1)%4); if(cnt==5) { ans++; } cnt=0;//用完置为0，不然数据就错了 memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); return; } for(int i=k+1; i<=12; i++) {//生成一个5个数序列，其实用next_permutation函数也行 num[step]=i; solve(step+1,i); } } int main() { solve(0,0); cout<<ans<<endl; return 0; }