本文主要是介绍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去重的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!