蓝桥杯第八届国赛第二题：瓷砖样式

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

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

样例

答案：101466

#include <iostream> 
#include <stdio.h>
#include <string.h>
#include <map>
#include <algorithm>
using namespace std;
const int w = 3, h = 10;  // 高 、宽 
int graph[w][h];  // 墙 
int ans = 0; //方案数 map<int, int> Hash; //用此来去重 //检查2x2格子颜色是否相同 
bool check_color() {for(int i = 0; i < w; i++) //行 for(int j = 0; j < h; j++) { //列 if(i+1 < w && j+1 < h) {if((graph[i][j]+graph[i][j+1]+graph[i+1][j]+graph[i+1][j+1]) % 4 == 0) return false; //相同 }}return true; //不同 
}void fill_with_tile(int x, int y) {if(x>w-1||y>h-1){return ;}//未访问 ; 每个位置共有两种摆放方式 if(graph[x][y] == -1) {  //方式一：横向摆放 前提: 该位置同行的下个格子有空才行 if(y+1 < h && graph[x][y+1] == -1) {// 0:黄色、1：橙色 for(int i = 0; i < 2; i++) { graph[x][y] = i;graph[x][y+1] = i;if(y == h-1) {  fill_with_tile(x+1, 0); //铺下一行} else {fill_with_tile(x, y+1); //铺当前行的下一个格子}graph[x][y] = -1;graph[x][y+1] = -1;}}//方式二： 纵向摆放 if(x+1 < w && graph[x+1][y] == -1) {// 0:黄色、1：橙色 for(int i = 0; i < 2; i++) {graph[x][y] = i;graph[x+1][y] = i;if(y == h-1) {  fill_with_tile(x+1, 0); //铺下一行} else {        fill_with_tile(x, y+1); //铺当前行的下一个格子}graph[x][y] = -1;graph[x+1][y] = -1;}}} //以访问 else {if(x == w-1 && y == h-1) { //成功铺满 if(check_color()) { //检查2x2格子颜色是否相同 //自编一个哈希函数，为此摆放方式确定一个键值 int ret = 0, bit = 1;for(int i = 0; i < w; i++){ for(int j = 0; j < h; j++) {ret += graph[i][j] * bit;bit *= 2;}} // count()函数返回map中键值等于key的元素的个数。 if(!Hash.count(ret)) { // 只有返回 0 时才会进入 Hash[ret] = 1;// 这个赋值是随意的 ans++;}}return;}//接下来的这对if~else就是核心 if(y == h-1) { fill_with_tile(x+1, 0); // 铺下一行} else {                fill_with_tile(x, y+1);// 铺当前行的下一个格子}}
}int main() {memset(graph, -1, sizeof(graph));//将数组初始化 fill_with_tile(0, 0); //从第一个位置开始 printf("%d\n", ans);return 0;
}

#include <iostream> 
#include <cstdio>using namespace std;
int a[5][12];
int count=0;//判断任意2*2的区域内颜色是否相同 ：不用担心数组越界问题 
bool judge(int x,int y){//作为右下角 if(a[x][y]==a[x-1][y-1] && a[x][y]==a[x-1][y] && a[x][y]==a[x][y-1])return false;// 作为左下角 if(a[x][y]==a[x-1][y] && a[x][y]==a[x-1][y+1] && a[x][y]==a[x][y+1])return false;// 作为右上角 if(a[x][y]==a[x][y-1] && a[x][y]==a[x+1][y-1] && a[x][y]==a[x+1][y])return false;// 作为左上角 if(a[x][y]==a[x][y+1] && a[x][y]==a[x+1][y] && a[x][y]==a[x+1][y+1])return false;return true;
}void dfs(int x,int y){  if(x==3&&y==10){ //铺满了 count++;return;}if(y>10){ //必不可少 dfs(x+1,1);return; //这个return也是用的超棒的 ,避免了重复计数 }//未被访问 if(a[x][y]==-1){if(a[x][y+1]==-1){ //如果它右边的位置可以访问 //贴黄色 a[x][y]=1;a[x][y+1]=1;if(judge(x,y)){ //这个很 dfs(x,y+1);}a[x][y]=-1;//回溯 a[x][y+1]=-1;//贴橙色 a[x][y]=2;a[x][y+1]=2;if(judge(x,y)){dfs(x,y+1);}a[x][y]=-1;a[x][y+1]=-1;}if(a[x+1][y]==-1){ //如果它下面的位置可以被访问 a[x][y]=1;a[x+1][y]=1;if(judge(x,y)){dfs(x,y+1);}a[x][y]=-1;a[x+1][y]=-1;a[x][y]=2;a[x+1][y]=2;if(judge(x,y)){dfs(x,y+1);}a[x][y]=-1;a[x+1][y]=-1;}}//已被访问 else{dfs(x,y+1);}}
int main(){for(int i=1;i<=3;i++){for(int j=1;j<=10;j++){a[i][j]=-1;}}//由于坐标是从1开始并且数组比原本的大因此不必考虑是否越界的问题 dfs(1,1);printf("%d",count);return 0;
}