如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下5张来，要求必须是连着的。 （仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。 请你计算，一共有多少种不同的剪取方法。 请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
116
两种实现判断连通块个数的方法：dfs，bfs
#include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstring> #include<vector> #include<map> #include<set> #include<queue> using namespace std; const int inf=0x3fffffff; const int maxn=10010; int n=3,m=4; int g[3][4]; //int a[12]={0,0,0,0,0,0,0,1,1,1,1,1}; int ans=0; int a[12]; int f[2]; int X[4]={0,0,-1,1}; int Y[4]={1,-1,0,0}; bool judge(int x,int y){ if(x<0||x>=n||y<0||y>=m) return false; if(g[x][y]==0) return false; return true; } void dfs(int x,int y){ g[x][y]=0; for(int i=0;i<4;i++){ int newX = x + X[i]; int newY = y + Y[i]; if(judge(newX,newY)) dfs(newX,newY); } } void permute(int idx){ if(idx==12){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) g[i][j]=a[i*m+j]; int res=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]==1){ dfs(i,j); res++; cout<<res<<endl; } if(res==1) ans++; return ; } for(int i=0;i<=1;i++){ if(f[i]){ f[i]--; a[idx]=i; permute(idx+1); f[i]++; a[idx]=-1; } } } int main(){ f[0]=7,f[1]=5; permute(0); cout<<ans<<endl; return 0; }#include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstring> #include<vector> #include<map> #include<set> #include<queue> using namespace std; const int inf=0x3fffffff; const int maxn=10010; int n=3,m=4; int g[3][4]; int a[12]={0,0,0,0,0,0,0,1,1,1,1,1}; struct node{ int x; int y; node(){} node(int _x,int _y) { x=_x, y=_y; } }; int X[4]={0,0,-1,1}; int Y[4]={1,-1,0,0}; bool inq[3][4]; bool judge(int x,int y){ if(x<0||x>=n||y<0||y>=m) return false; if(g[x][y]==0) return false; if(inq[x][y]==true) return false; return true; } void bfs(int x,int y){ int newX,newY; queue<node> q; node tmp = node(x,y); q.push(tmp); inq[x][y]=true; while(!q.empty()){ node top = q.front(); q.pop(); for(int i=0;i<4;i++){ newX = top.x + X[i]; newY = top.y + Y[i]; if(judge(newX,newY)){ tmp = node(newX,newY); q.push(tmp); inq[tmp.x][tmp.y]=true; } } } } void dfs(int x,int y){ g[x][y]=0; if(x-1>=0 && g[x-1][y]==1) dfs(x-1,y); if(x+1<n && g[x+1][y]==1) dfs(x+1,y); if(y-1>=0 && g[x][y-1]==1) dfs(x,y-1); if(y+1<m && g[x][y+1]==1) dfs(x,y+1); } int main(){ int ans=0; do{ for(int i=0;i<n;i++) for(int j=0;j<m;j++) g[i][j]=a[i*m+j]; // memset(inq,false,sizeof(inq)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) inq[i][j]=false; int res=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(g[i][j]==1&&inq[i][j]==false){ bfs(i,j); res++; } // if(g[i][j]==1){ // // dfs(i,j); // res++; // } } } if(res==1) ans++; }while(next_permutation(a,a+12)); cout<<ans<<endl; return 0; } #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstring> #include<vector> #include<map> #include<set> #include<queue> using namespace std; const int inf=0x3fffffff; const int maxn=10010; int n=3,m=4; int g[3][4]; int a[12]={0,0,0,0,0,0,0,1,1,1,1,1}; struct node{ int x; int y; node(){} node(int _x,int _y) { x=_x, y=_y; } }; int X[4]={0,0,-1,1}; int Y[4]={1,-1,0,0}; bool inq[3][4]; bool judge(int x,int y){ if(x<0||x>=n||y<0||y>=m) return false; if(g[x][y]==0) return false; if(inq[x][y]==true) return false; return true; } void bfs(int x,int y){ int newX,newY; queue<node> q; node tmp = node(x,y); q.push(tmp); g[x][y]=0; while(!q.empty()){ node top = q.front(); q.pop(); for(int i=0;i<4;i++){ newX = top.x + X[i]; newY = top.y + Y[i]; if(judge(newX,newY)){ tmp = node(newX,newY); q.push(tmp); g[newX][newY]=0; } } } } int main(){ int ans=0; do{ for(int i=0;i<n;i++) for(int j=0;j<m;j++) g[i][j]=a[i*m+j]; memset(inq,false,sizeof(inq)); int res=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]==1 ){ bfs(i,j); res++; } if(res==1) ans++; }while(next_permutation(a,a+12)); cout<<ans<<endl; return 0; }
