标题：磁砖样式
小明家的一面装饰墙原来是 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 #include #include 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; }
