蓝桥杯16届第7题——剪邮票（bfs、dfs、控制变量）

末蓝、 2023-07-25 14:26 24阅读 0赞

## 剪邮票题目 ##

2016年蓝桥杯剪邮票原题：

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

--------------------

题意：在3 \* 4的表格中，选择连通的5张邮票，判断能有多少种不同选法。  
**难点在于如何判断组合是否符合题意。**

##### 初步思路：单纯bfs #####

通过bfs得出一条可行路径。你会发现最终结果并不包含图3。图3是在图形存在“分支”，并不是一路到底。

//单纯
    #include<bits/stdc++.h>
    using namespace std;
    
    struct node{ 
    	int x;
    	int y;
    	int step;
    	bool a[3][4];
    }Node, top;
    
    int ans=0;
    int X[2] = { 1, 0};
    int Y[2] = { 0, 1};
    int XX[3] = { 1, 0, 0}; 
    int YY[3] = { 0, 1, -1}; 
    	
    bool judge(node A, int x, int y)
    { 
    	if(x>=3||y>=4||x<0||y<0||A.a[x][y]==true) 
    		return false;
    	return true;
    }
    
    void bfs(int x, int y)	//没有分支 
    { 
    	Node.x = x;
    	Node.y = y;
    	Node.step=1; 
    	for(int i=0; i<3; i++)	//初始化 
    	for(int j=0; j<4; j++)
    		Node.a[i][j]=false; 
    	Node.a[x][y]=true;
    	queue <node> q;
    	q.push(Node);
    	
    	while(!q.empty())
    	{ 
    		top=q.front();
    		if(top.step==6) 
    		{ 
    			q.pop();
    			continue;
    		}
    		int Xi = top.x;
    		int Yi = top.y;
    		if(top.step==5) 
    		{ 
    			cout<<top.step<<endl;
    			for(int i=0; i<3; i++)
    			{ 
    				for(int j=0; j<4; j++)
    				cout<<top.a[i][j]<<" ";
    				cout<<endl;
    			}
    		}
    		if(top.step==5)
    		ans++;
    		for(int i=0; i<2&&top.step==1; i++)
    		{ 
    			if(judge(top, Xi+X[i], Yi+Y[i])&&top.step==1)//第二步：只能向下或向右 
    			{ 
    				for(int i=0; i<3; i++)
    				for(int j=0; j<4; j++)
    				Node.a[i][j] = top.a[i][j];
    				
    				Node.a[Xi+X[i]][Yi+Y[i]]=true;
    				Node.x=Xi+X[i];
    				Node.y=Yi+Y[i];
    				Node.step=top.step+1;
    				
    				q.push(Node);
    			}
    		}
    		for(int i=0; i<3&&top.step>1; i++)
    		{ 
    			if(judge(top, Xi+XX[i], Yi+YY[i]))//第二步后：只能向下或向左、向右 
    			{ 
    				for(int i=0; i<3; i++)
    				for(int j=0; j<4; j++)
    				Node.a[i][j] = top.a[i][j];
    				
    				Node.a[Xi+XX[i]][Yi+YY[i]]=true;
    				Node.x=Xi+XX[i];
    				Node.y=Yi+YY[i];
    				Node.step=top.step+1;
    				q.push(Node);
    			}
    		}
    		q.pop();
    	}
    }
    
    int main()
    { 
    	for(int i=0; i<3; i++)	//不同的开头，没有分支 
    	for(int j=0; j<4; j++)
    	bfs(i, j);
    
    	cout<<ans;
    	
    	return 0;
    }

##### 改进思路：暴力法，在12个格子，直接枚举5个格子。dfs判断是否连通。 #####

注意：  
一、要避免5个相同格子被重复选取。  
二、在一维转二维时，注意将k控制在(0~4)之间，防止数组sz2被越界访问。

#include<bits/stdc++.h>
    using namespace std;
    int sz[12]={ 1,2,3,4,5,6,7,8,9,10,11,12};
    int sz2[3][4];
    int a[5], ans=0;
    int X[4]={ 0, 0, 1, -1};
    int Y[4]={ 1, -1, 0, 0};
    void dfs2(int x, int y)
    { 
    	sz2[x][y]=0;
    	for(int i=0; i<4; i++)
    	if(sz2[x+X[i]][y+Y[i]]==1&&x+X[i]>=0&&x+X[i]<3&&y+Y[i]>=0&&y+Y[i]<4)
    	dfs2(x+X[i],y+Y[i]);
    }
    
    bool judge(int a[5])
    { 
    	int k=0;
    	 
    	for(int i=0; i<3; i++)
    	{ 
    		for(int j=0; j<4; j++)
    		{ 
    			if(4*i+j+1==a[k])
    			{ 
    				if(k<5)		//防止k越界访问
    				sz2[i][j]=1;
    				k++;
    			}
    		}
    	}
    	int buf=0;
    	for(int i=0; i<3; i++)
    	for(int j=0; j<4; j++)
    	{ 
    		if(sz2[i][j]==1)
    		{ 
    			buf++;
    			dfs2(i, j);
    		}
    	}
    	
    	return buf==1;
    }
    
    void dfs(int a[5], int k, int begin)
    { 
    	if(k==5)
    	{ 
    		if(judge(a))
    		{ 
    			ans++;
    			for(int i=0; i<5; i++)
    			cout<<a[i]<<" ";
    			cout<<endl;
    		}
    		return;
    	}
    	
    	for(int i=begin+1; i<12; i++)	//12位取5位，不重复 
    	{ 
    		a[k]=i+1;
    		dfs(a, k+1, i);
    	}
    }
    
    int main()
    { 
    	memset(a, 0, sizeof(a));
    	for(int i=0; i<9; i++)
    	{ 
    		a[0]=i+1;
    		dfs(a, 1, i);
    	}
    	
    	cout<<ans;
    	return 0;
    }

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[1]: /images/20230528/d696ad3e63cb4a22ba96aed87a7a8e3d.png
[2]: /images/20230528/6eef5630735e417d8753ed055176d78a.png
[3]: /images/20230528/3b32aaaf77144b299e442edee7489aa3.png