第八届蓝桥杯国赛C++B组 磁砖样式

标题：磁砖样式

小明家的一面装饰墙原来是 3*10 的小方格。
现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色：黄色和橙色。

小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。
小明有个小小的强迫症：忍受不了任何2*2的小格子是同一种颜色。
（瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝）
显然，对于 2*3 个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】

但对于 3*10 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。

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

答案：101466

思路：一直觉得这道题的特色，是它的标题有错别字hhhhh 可以一行一行的来贴瓷砖，有四种情况，横向贴【(x,y)、(x,y+1)】和纵向贴【(x,y)、(x+1,y)】，分别2种颜色（用0和1表示）。每次贴满一种情况的时候，检查一个2*2内有没有同一种颜色，然后再检查整体的情况有没有重复，这里用一个30位长的二进制来记录一种情况，方便检查重复，参考的这位大佬（https://www.cnblogs.com/flyawayl/p/8503152.html）

代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;

int wall[3][10], ans = 0;
map<int, int> mp;

void dfs(int x, int y)
{
	if (wall[x][y] == -1)
	{
		if (y < 9 && wall[x][y + 1] == -1)//横向 
		{
			for (int i = 0; i < 2; i++)//两种颜色 
			{
				wall[x][y] = wall[x][y + 1] = i;
				dfs(x, y + 1);
				wall[x][y] = wall[x][y + 1] = -1;
			}
		}
		if (x < 2 && wall[x + 1][y] == -1)//纵向 
		{
			for (int i = 0; i < 2; i++)//两种颜色 
			{
				wall[x][y] = wall[x + 1][y] = i;
				if (y == 9)//当前行贴满了，转到下一行 
					dfs(x + 1, 0);
				else
					dfs(x, y + 1);
				wall[x][y] = wall[x + 1][y] = -1;
			}
		}
	}
	else
	{
		if (x == 2 && y == 9)//贴满了 
		{
			bool flag = true;
			for (int i = 0; i < 2; i++)
			{
				for (int j = 0; j < 9; j++)
				{
					if ((wall[i][j] + wall[i][j + 1] + wall[i + 1][j] + wall[i + 1][j + 1]) % 4 == 0)//2*2内颜色相同 
					{
						flag = false;
						break;
					}
				}
			}
			if (flag)
			{
				int n = 0;
				for (int i = 0; i < 3; i++)
				{
					for (int j = 0; j < 10; j++)
						n = n * 2 + wall[i][j];
				}
				mp[n]++;
				if (mp[n] == 1)
					ans++;
			}
		}
		if (y == 9)//当前行贴满了，转到下一行 
			dfs(x + 1, 0);
		else
			dfs(x, y + 1);
	}
}

int main()
{
	memset(wall, -1, sizeof(wall));
	dfs(0, 0);
	cout << ans << endl;
	return 0;
}