欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

原理详解与标准解法——蓝桥杯_2016年省赛B组 第七题 剪邮票(暴力+迷宫变形)

程序员文章站 2022-04-14 08:21:19
如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来,要求必须是连着的。(仅仅连接一个角不算相连)比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合> 格的剪取。分析与题解本着暴力出奇迹的原则,先用暴力法的思想考虑了一通, 发现用暴力法完全没办法判断格子的连通性, 于是转向DFS解法。正常考虑:每个格子作为起点,DFS连五张格子,最后去重, 最终得到最后结果。但由于正常情况下DFS没办法同时向两个方向保持探索, 因此无法解决T型剪纸的问题,如....

如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来,要求必须是连着的。(仅仅连接一个角不算相连)比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合> 格的剪取。
原理详解与标准解法——蓝桥杯_2016年省赛B组  第七题  剪邮票(暴力+迷宫变形)
原理详解与标准解法——蓝桥杯_2016年省赛B组  第七题  剪邮票(暴力+迷宫变形)

分析与题解

本着暴力出奇迹的原则,先用暴力法的思想考虑了一通, 发现用暴力法完全没办法判断格子的连通性, 于是转向DFS解法。

正常考虑:每个格子作为起点,DFS连五张格子,最后去重, 最终得到最后结果。但由于正常情况下DFS没办法同时向两个方向保持探索, 因此无法解决T型剪纸的问题,如
原理详解与标准解法——蓝桥杯_2016年省赛B组  第七题  剪邮票(暴力+迷宫变形)

那么如何检测T型剪纸呢?
我们可以通过循环暴力求解出剪出5个格子的所有方案, 对每个方案进行连通性检测(类似迷宫), 若连通,则累加, 最后输出累加结果。

注意:在设定mp数组时,将{1,2,3,4,5,6,7,8,9,10,11,12}改为{1,2,3,4, 6,7,8,9, 11,12,13,14} 即可轻松判断某一格子是否在其两侧或上下

最后贴上代码,代码中有详细的注释。


代码展示

#include<iostream>
#include<algorithm>
using namespace std;
int mp[12] = {1,2,3,4, 6,7,8,9, 11,12,13,14};	 
int aa[5];			//五个格子的编号 
int vis[5];			//每个格子是否被访问过 
int sum = 0;		//结果 
int b[4] = {-1, 1, -5, +5};		//通过b数组检测是否有格子连通 

void dfs(int n) {		//检测连通性 
	for(int i = 0; i < 4; i++) {	//遍历b数组,检测格子的联通性 
		int t = aa[n] + b[i];		//用t存储 
		if(t<1 || t>14 || t==5 || t==10) continue;//t值不规范,结束本层循环 
		
		//从0开始, 
		for(int j = 0; j < 5; j++) 	//开始检测五个格子中的每个格子是否与编号为n的格子连通 
			if(!vis[j] && aa[j]==t) {	//若某格子既没被访问过,又与编号为n的格子连通 
				vis[j] = 1;			//该格子改为被访问过 
				dfs(j);				//从该格子开始继续向下dfs 
			}
	}
}


int main() {
	ios::sync_with_stdio(false);	//加快c++速度 
	for(int a = 0; a < 12; a++) 	//五层循环,寻找任意5格子。 
	for(int b = a+1; b < 12; b++)
	for(int c = b+1; c < 12; c++) 
	for(int d = c+1; d < 12; d++)
	for(int e = d+1; e < 12; e++) {	
		aa[0]=mp[a]; aa[1]=mp[b]; aa[2]=mp[c]; aa[3]=mp[d]; aa[4]=mp[e];	//赋值 
		
		for(int i = 0; i < 5; i++) vis[i] = 0;	//每次判断前先初始化 
		
		vis[0] = 1;		//从第一个格子开始,因此第一个格子一定被访问过 
		dfs(0); 		//从0开始回溯 
		int flag = 1;
		for(int i = 0; i < 5; i++) 	//最后判断5个格子是否都被访问过,若是,则连通。 
			if(vis[i] != 1) {
				flag = 0; break;
			}
		if(flag == 0) continue;
		else sum++;
	} 
	cout << sum << endl;
return 0; }

这世界就是,一些人总在昼夜不停的努力,而另外一些人,起床就发现世界已经变了。

本文地址:https://blog.csdn.net/weixin_43899069/article/details/108682257