磁砖样式

小明家的一面装饰墙原来是 310 的小方格。

现在手头有一批刚好能盖住2个小方格的长方形瓷砖。

瓷砖只有两种颜色:黄色和橙色。

小明想知道,对于这么简陋的原料,可以贴出多少种不同的花样来。

小明有个小小的强迫症:忍受不了任何2
2的小格子是同一种颜色。

(瓷砖不能切割,不能重叠,也不能只铺一部分。另外,只考虑组合图案,请忽略瓷砖的拼缝)

显然,对于 23 个小格子来说,口算都可以知道:一共10种贴法,如【p1.png所示】

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

注意:你需要提交的是一个整数,不要填写任何多余的内容(比如:说明性文字)

2017第八届蓝桥杯决赛(C++ B组)2.磁砖样式-LMLPHP

解题思路

暴力枚举解答树,然后判断该解是否可行

源码

#include <iostream>
int cnt = 0; #define COLOR_ORANGE 1
#define COLOR_YELLOW 2 int cell[3][10]{ 0 }; bool isOK() {
for (int x = 1; x < 3; x++) {
for (int y = 1; y < 10; y++) {
if (cell[x - 1][y - 1] == cell[x][y]&& cell[x][y] == cell[x - 1][y]&& cell[x][y] == cell[x][y - 1]) {
return false;
}
}
} return true;
} void fill(int x, int y) {
if (x == 3) {
if (isOK()) {
cnt++;
/*std::cout << "-------------------\n";
for (int i = 0; i < 3; i++) {
for (int k = 0; k < 10; k++) {
std::cout << cell[i][k] << " ";
}
std::cout << "\n";
}*/
}
return;
}
for (int p = 1; p <= 2; p++) {
if (y + 1 < 10 && cell[x][y] == 0 && cell[x][y + 1] == 0) {
cell[x][y] = p;
cell[x][y + 1] = p;
if (y == 8) {
fill(x + 1, 0);
}
else {
fill(x, y + 2);
}
cell[x][y] = 0;
cell[x][y + 1] = 0;
} if (x + 1 <= 3 && cell[x][y] == 0 && cell[x + 1][y] == 0) {
cell[x][y] = p;
cell[x + 1][y] = p;
if (y == 9) {
fill(x + 1, 0);
}
else {
fill(x, y + 1);
}
cell[x][y] = 0;
cell[x + 1][y] = 0;
}
}
} int main(){
fill(0, 0);
std::cout << cnt;
return 0;
}
05-11 18:14