标题:磁砖样式
小明家的一面装饰墙原来是 3*10 的小方格。
现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色:黄色和橙色。
小明想知道,对于这么简陋的原料,可以贴出多少种不同的花样来。
小明有个小小的强迫症:忍受不了任何2*2的小格子是同一种颜色。
(瓷砖不能切割,不能重叠,也不能只铺一部分。另外,只考虑组合图案,请忽略瓷砖的拼缝)
显然,对于 2*3 个小格子来说,口算都可以知道:一共10种贴法,如【p1.png所示】
但对于 3*10 的格子呢?肯定是个不小的数目,请你利用计算机的威力算出该数字。
注意:你需要提交的是一个整数,不要填写任何多余的内容(比如:说明性文字)
Ideas
统计总数,一看就想到用DFS。
1、首先,确定一个检查函数,判断瓷砖铺设是否符合要求;
2、3*10的地板,每一列上肯定是一个竖着的,一个横着的,或者三块横着的;
3.深搜算法,先判断当前位置是否已经存在瓷砖,然后判断在边界内当前位置的下方和左方是否已经存在瓷砖:
3.1、如果左边没有瓷砖,直接铺一块横着的瓷砖然后继续深搜
4.用0表示还未铺设瓷砖,1表示黄色瓷砖,2表示橙色瓷砖;
Code
C++
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
map<int, int> Hash;
int ans = 0, graph[3][10];
bool check() {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 9; j++)
if ((graph[i][j] + graph[i][j + 1] + graph[i + 1][j] + graph[i + 1][j + 1]) % 4 == 0)
return false;
return true;
}
void dfs(int x, int y) {
if (graph[x][y] == -1) {
//横向铺设
if (y < 9 && graph[x][y + 1] == -1) {
for (int i = 0; i < 2; i++) {
graph[x][y] = graph[x][y + 1] = i;
dfs(x, y + 1);
graph[x][y] = graph[x][y + 1] = -1;
}
}
//纵向铺设
if (x < 2 && graph[x + 1][y] == -1) {
for (int i = 0; i < 2; i++) {
graph[x][y] = graph[x + 1][y] = i;
if (y == 9) dfs(x + 1, 0);
else dfs(x, y + 1);
graph[x][y] = graph[x + 1][y] = -1;
}
}
} else {
if (x == 2 && y == 9) {
if (check()) {
int ret = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 10; j++)
ret = ret * 2 + graph[i][j];
Hash[ret]++;
if (Hash[ret] == 1)
ans++;
}
return;
}
if (y == 9) dfs(x + 1, 0);
else dfs(x, y + 1);
}
}
int main() {
memset(graph, -1, sizeof(graph));
dfs(0, 0);
cout << ans << endl;
return 0;
}