2017年第八届蓝桥杯C/C++ B组国赛 —— 第二题：瓷砖样式
程序员文章站
2024-02-10 20:01:28
...
标题：磁砖样式
小明家的一面装饰墙原来是 3*10 的小方格。
现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色：黄色和橙色。
小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。
小明有个小小的强迫症：忍受不了任何2*2的小格子是同一种颜色。
（瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝）
显然，对于 2*3 个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】
但对于 3*10 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。
注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）
Code
/*
^....0
^ .1 ^1^
.. 01
1.^ 1.0
^ 1 ^ ^0.1
1 ^ ^..^
0. ^ 0^
.0 1 .^
.1 ^0 .........001^
.1 1. .111100....01^
00 11^ ^1. .1^
1.^ ^0 0^
.^ ^0..1
.1 1..^
1 .0 ^ ^
00. ^^0.^
^ 0 ^^110.^
0 0 ^ ^^^10.01
^^ 10 1 1 ^^^1110.1
01 10 1.1 ^^^1111110
010 01 ^^ ^^^1111^1.^ ^^^
10 10^ 0^ 1 ^^111^^^0.1^ 1....^
11 0 ^^11^^^ 0.. ....1^ ^ ^
1. 0^ ^11^^^ ^ 1 111^ ^ 0.
10 00 11 ^^^^^ 1 0 1.
0^ ^0 ^0 ^^^^ 0 0.
0^ 1.0 .^ ^^^^ 1 1 .0
^.^ ^^ 0^ ^1 ^^^^ 0. ^.1
1 ^ 11 1. ^^^ ^ ^ ..^
^..^ ^1 ^.^ ^^^ .0 ^.0
0..^ ^0 01 ^^^ .. 0..^
1 .. .1 ^.^ ^^^ 1 ^ ^0001
^ 1. 00 0. ^^^ ^.0 ^.1
. 0^. ^.^ ^.^ ^^^ ..0.0
1 .^^. .^ 1001 ^^ ^^^ . 1^
. ^ ^. 11 0. 1 ^ ^^ 0.
0 ^. 0 ^0 1 ^^^ 0.
0.^ 1. 0^ 0 .1 ^^^ ..
.1 1. 00 . .1 ^^^ ..
1 1. ^. 0 .^ ^^ ..
0. 1. .^ . 0 .
.1 1. 01 . . ^ 0
^.^ 00 ^0 1. ^ 1 1
.0 00 . ^^^^^^ .
.^ 00 01 ..
1. 00 10 1 ^
^.1 00 ^. ^^^ .1
.. 00 .1 1..01 ..
1.1 00 1. ..^ 10
^ 1^ 00 ^.1 0 1 1
.1 00 00 ^ 1 ^
. 00 ^.^ 10^ ^^
1.1 00 00 10^
..^ 1. ^. 1.
0 1 ^. 00 00 .^
^ ^. ^ 1 00 ^0000^ ^ 01
1 0 ^. 00.0^ ^00000 1.00.1 11
. 1 0 1^^0.01 ^^^ 01
.^ ^ 1 1^^ ^.^
1 1 0.
.. 1 ^
1 1
^ ^ .0
1 ^ 1
.. 1.1 ^0.0
^ 0 1..01^^100000..0^
1 1 ^ 1 ^^1111^ ^^
0 ^ ^ 1 1000^
.1 ^.^ . 00
.. 1.1 0. 0
1. . 1. .^
1. 1 1. ^0
^ . ^.1 00 01
^.0 001. .^
*/
// VB_king —— 2017_Finals_B_2.cpp created by VB_KoKing on 2019-05-06:07.
/* Procedural objectives：
Variables required by the program:
Procedural thinking：
1、首先，确定一个检查函数，判断瓷砖铺设是否符合要求；
2、3*10的地板，每一列上肯定是一个竖着的，一个横着的，或者三块横着的；
3、深搜算法，先判断当前位置是否已经存在瓷砖；
3.1、如果当前位置没有瓷砖，看当前列的瓷砖情况：
3.1.1、如果在第一、三行上，
3.1.1.1、在当前位置铺一块横着的瓷砖，剩下两个铺一块竖着的瓷砖；
3.1.1.2、在当前位置铺一块竖着的瓷砖，剩下一个铺一块横着的瓷砖；
3.1.2、如果在第二行上，
3.2、如果当前位置有瓷砖，看当前列的瓷砖情况：
思路太麻烦，情况太多，不易分析。
3.深搜算法，先判断当前位置是否已经存在瓷砖，然后判断在边界内当前位置的下方和左方是否已经存在瓷砖：
3.1、如果左边没有瓷砖，直接铺一块横着的瓷砖然后继续深搜
4.用0表示还未铺设瓷砖，1表示黄色瓷砖，2表示橙色瓷砖；
Functions required by the program:
1、检查瓷砖铺设是否符合要求的函数bool check(int graph[3][10]);
2、检查瓷砖是否铺满的函数bool is_full(int graph[3][10]);
Determination algorithm:
DFS+回溯
Determining data structure:
栈
*/
/* My dear Max said：
"I like you,
So the first bunch of sunshine I saw in the morning is you,
The first gentle breeze that passed through my ear is you,
The first star I see is also you.
The world I see is all your shadow."
FIGHTING FOR OUR FUTURE！！！
*/
#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;
}
上一篇： ＜3＞springboot集成jsp
下一篇： Springboot集成jsp