2016 蓝桥杯省赛剪邮票（dfs+判重）

淡淡的烟草味﹌ 2024-02-17 20:35 71阅读 0赞

剪邮票  
  
如【图1.jpg】, 有12张连在一起的12生肖的邮票。  
现在你要从中剪下5张来，要求必须是连着的。  
（仅仅连接一个角不算相连）  
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。  
  
请你计算，一共有多少种不同的剪取方法。  
  
请填写表示方案数目的整数。  
![Image 1][]

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：116

借鉴网上一个大神的代码，通过dfs+判重做出来了。

如果说用单纯的dfs做的话，像2 5 6 7 10 是无法出来的，所以用剪下来的进行dfs判断就不会漏掉这类情况了

代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10000;
    int hash[maxn];
    int vis[3][4];
    int tol;
    int dir[4][2]={
       {-1,0},{1,0},{0,1},{0,-1}};
    void dfs(int cnt){
    	if(cnt==5){
    		int tmp=0;
    		for(int i=0;i<3;i++){
    			for(int j=0;j<4;j++)
    			{
    				tmp=tmp<<1;
    				tmp+=vis[i][j];
    			}
    		}
    		if(!hash[tmp]){  //判重 
    			tol++; 
    			hash[tmp]=1;
    		}
    		return ;
    	}
    	
    	for(int i=0;i<3;i++){
    		for(int j=0;j<4;j++){
    			if(vis[i][j]){
    				for(int k=0;k<4;k++){
    				int x=dir[k][0]+i;
    				int y=dir[k][1]+j;
    				if(x<0 || x>=3 || y<0 || y>=4)continue;
    				if(!vis[x][y]){
    					vis[x][y]=1;
    					dfs(cnt+1);
    					vis[x][y]=0;
    				}
    			}
    	   	  } 
    		}
    	}
    }
    int main(){
    	tol=0;
    	memset(vis,0,sizeof(vis));
    	memset(hash,0,sizeof(hash));
    	for(int i=0;i<3;i++){
    		for(int j=0;j<4;j++){
    			vis[i][j]=1;
    			dfs(1);
    			vis[i][j]=0;
    		}
    	}
    	printf("%d\n",tol);
    	return 0;
    }

[Image 1]: