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

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

如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合> 格的剪取。

分析与题解

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

正常考虑：每个格子作为起点，DFS连五张格子，最后去重，最终得到最后结果。但由于正常情况下DFS没办法同时向两个方向保持探索，因此无法解决T型剪纸的问题，如

那么如何检测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; }