2017 蓝桥杯决赛 C++B（2）瓷砖样式 dfs + hash去重

本文主要是介绍2017 蓝桥杯决赛 C++B（2）瓷砖样式 dfs + hash去重，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

标题：磁砖样式

小明家的一面装饰墙原来是 3*10 的小方格。
现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色：黄色和橙色。
小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。
小明有个小小的强迫症：忍受不了任何2*2的小格子是同一种颜色。
（瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝）
显然，对于 2*3 个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】
但对于 3*10 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。

注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<map>
using namespace std;int mp[4][11];
map<int,int> hash;
int tol;bool noSame()//判断是否存在4个方块同样 {for(int i = 1; i <= 2; ++i){for(int j = 1; j <= 9; ++j){if(mp[i][j] == mp[i+1][j] && mp[i+1][j] == mp[i][j+1] && mp[i][j+1] == mp[i+1][j+1])return false;}}return true;}void color(int x, int y, int type,int v)//根据type判断水平2块还是数值2块  染成 v {if(type == 1){ //水平 for(int i = x; i < x+1; ++i){for(int j = y; j < y+2; ++j){mp[i][j] = v;}}}else if(type == 2){for(int i = x; i < x+2; ++i){for(int j = y; j < y+1; ++j){mp[i][j] = v;}}}}
bool checkX(int x, int y)//判断X方向是否能放2块 {if(x+1 > 3 || y > 10)return false;for(int i = x; i < x+2; ++i){for(int j = y; j < y+1; ++j){if(mp[i][j])return false;}}return true;}void output(){for(int i = 1; i <= 3; ++i){for(int j = 1; j <= 10; ++j){printf("%d",mp[i][j]);}printf("\n");}}	bool checkY(int x, int y)//判断y方向能否放2块 {if(x > 3 || y+1 > 10)return false;for(int i = x; i < x+1; ++i){for(int j = y; j < y+2; ++j){if(mp[i][j])return false;}}	return true;}void dfs(int x, int y){if(x > 3){if(noSame()){int bit = 1;long long ans = 0;for(int i = 1; i <= 3; ++i){for(int j = 1; j <= 10; ++j){ans += bit*mp[i][j];//用ans来标识唯一的涂色方案bit <<= 1;}}if(!hash[ans]){++tol;++hash[ans];}}return ;}	if(mp[x][y] == 0){if(checkX(x,y)){for(int i = 1; i <= 2; ++i){//注意瓷砖有2种 可以染不同颜色 color(x,y,2,i);if(y == 10){dfs(x+1,1);}else{dfs(x,y+1);}color(x,y,2,0);}}if(checkY(x,y)){for(int i = 1; i <= 2; ++i){color(x,y,1,i);if(y == 10){dfs(x+1,1);}else{dfs(x,y+1);}color(x,y,1,0);}}}else{if(y == 10){dfs(x+1,1);}else{dfs(x,y+1);}}}int main(){memset(mp,0,sizeof(mp));dfs(1,1);printf("%d",tol);return 0;}

这篇关于2017 蓝桥杯决赛 C++B（2）瓷砖样式 dfs + hash去重的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---