剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
思路:用数组b[ ]生成12个位置的全排列,然后把数组b赋值给数组map
然后深搜判断连通性,如果连通性为1,满足
答案: 116
代码:
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int a[12]={0,0,0,0,0,0,0,1,1,1,1,1}; int map[3][4]; int visit[3][4]; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; void dfs(int x,int y){ visit[x][y] = 1; for(int i=0;i<4;i++){ int xx = x+dx[i]; int yy = y+dy[i]; if(xx<0||xx>=3||yy<0||yy>=4) continue; if(map[xx][yy]&&!visit[xx][yy]){ dfs(xx,yy); } } } int main(){ int ans = 0; do{ int cnt = 0; memset(map,0,sizeof(map)); for(int i=0;i<3;i++){ for(int j=0;j<4;j++){ map[i][j] = a[cnt++]; visit[i][j] = 0; } } int t=0; for(int i=0;i<3;i++){ for(int j=0;j<4;j++){ if(map[i][j]==1&&!visit[i][j]){ t++; dfs(i,j); } } } if(t==1) ans++; }while(next_permutation(a,a+12)); cout<<ans<<endl; return 0; }