2017蓝桥杯C/C++B组国赛-瓷砖样式

题目

题目链接

题解

DFS。

方案需要满足的要求：

1. 只能有黄和橙两种颜色；
2. 必须填满；
3. 任何一种颜色都不允许同时出现在 2 × 2 2×2 2×2 的方格中；
4. 任意一种颜色图案都必须能由 2 × 1 2×1 2×1 或 1 × 2 1×2 1×2 的长方形瓷砖拼成；
5. 瓷砖不能切割，不能重叠，也不能只铺一部分；
6. 只考虑组合图案，忽略瓷砖的拼缝.

举几个反例：

最后一种容易忽略。

想过二进制枚举，但是二进制枚举的话，对于枚举到的每种状态不好判断是否满足要求。所以还是得用DFS。

由于要求两种颜色的图案都要能用 2 × 1 2×1 2×1 或 1 × 2 1×2 1×2 的瓷砖拼成，所以遍历到某个格子时要分别尝试着贴黄色瓷砖和橙色瓷砖。

（如果要是只dfs一种颜色的瓷砖，另一种颜色的瓷砖贴在剩下的地方，那么这无法保证剩下的位置一定能由 2 × 1 2×1 2×1 或 1 × 2 1×2 1×2 的瓷砖拼成。你说你想在找到方案时判断一下另一种颜色的图案是否可行，这不又回归到为什么二进制枚举不好实现了嘛）

如果遍历到的这个格子已经贴上了瓷砖，那么就不能再贴瓷砖了，继续判断下一个位置；如果遍历到的格子没贴上瓷砖，则必须在这个位置贴上瓷砖（“必须填满”），可以选择黄色或橙色。对于要贴瓷砖的情况，可以选择向上下贴，也可以选择左右贴。

我们按照从上往下，从左到右的顺序DFS，即先看第一行的每一列，再看第二行的每一列。当到达每一列的倒数第二块瓷砖时，我们就要将DFS的参数调整为下一行的第一个瓷砖了。

对于上图中的第三种不合法情况，我们没有什么好的技巧，只能通过 m a p map map 存起来，每次判断完 2 × 2 2×2 2×2 的方格中是否并非全色，之后再去判断该方案是否已经保存过，没保存过说明这是新方案，统计一下。

对于方案的保存，我们可以使用二进制的方式，因为总共两种颜色。

代码

#include
using namespace std;

const int N = 3, M = 10;

int vis[N+1][M+1], ans;
unordered_map hash_;

bool check () {
	for (int i = 1;i