2017第八届蓝桥杯决赛 磁砖样式
程序员文章站
2022-05-30 21:26:27
...
标题:磁砖样式
小明家的一面装饰墙原来是 3*10 的小方格。现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色:黄色和橙色。
小明想知道,对于这么简陋的原料,可以贴出多少种不同的花样来。
小明有个小小的强迫症:忍受不了任何2*2的小格子是同一种颜色。
(瓷砖不能切割,不能重叠,也不能只铺一部分。另外,只考虑组合图案,请忽略瓷砖的拼缝)
显然,对于 2*3 个小格子来说,口算都可以知道:一共10种贴法,如【p1.png所示】
但对于 3*10 的格子呢?肯定是个不小的数目,请你利用计算机的威力算出该数字。
注意:你需要提交的是一个整数,不要填写任何多余的内容(比如:说明性文字)
答案:114434
分析:刚开始想暴力枚举2^30种情况,然后筛选满足情况的个数,后面发现不好筛选满足情况的个数,而且时间复杂度过大,看来还是得用搜索,具体细节代码中都有详细的注释。
代码:
#include<bits/stdc++.h>
using namespace std;
int a[5][12];///-1代表未摆放,1代表黄色,2代表橙色
///申请5*12的空间为方便对3*10的方格进行2*2的判断
///只能对3*10的方格进行赋值,保证第0/4行、第0/11列
int res;
int ck(int x,int y) {
if( a[x][y] == a[x-1][y-1] && a[x][y] == a[x-1][y] && a[x][y] == a[x][y-1] ) return 0;
if( a[x][y] == a[x-1][y+1] && a[x][y] == a[x-1][y] && a[x][y] == a[x][y+1] ) return 0;
if( a[x][y] == a[x+1][y-1] && a[x][y] == a[x][y-1] && a[x][y] == a[x+1][y] ) return 0;
///if( a[x][y] == a[x+1][y+1] && a[x][y] == a[x][y+1] && a[x][y] == a[x+1][y] ) return 0;
///右下方的情况 不需要判断 因为还未搜索到 肯定不满足条件
return 1;
}
///从坐上到右下依次填方格
void dfs(int x,int y) {
if(x==3&&y==10) {
res++;
return ;
}
if(y>10) { ///注意return 防止重复计数
dfs(x+1,1);
return ;
}
if(a[x][y]==-1) {
if( a[x][y+1] == -1 ) { ///横
a[x][y] = a[x][y+1] = 1; ///黄色
if(ck(x,y)) dfs(x,y+1);
///a[x][y] = a[x][y+1] = -1;///回溯 还原
a[x][y] = a[x][y+1] = 2; ///橙色
if(ck(x,y)) dfs(x,y+1);
a[x][y] = a[x][y+1] = -1;
}
if( a[x+1][y] == -1) { ///竖
a[x][y] = a[x+1][y] = 1;
if(ck(x,y)) dfs(x,y+1);
///a[x][y] = a[x+1][y] = -1;
a[x][y] = a[x+1][y] = 2;
if(ck(x,y)) dfs(x,y+1);
a[x][y] = a[x+1][y] = -1;
}
}else dfs(x,y+1);
}
int main() {
for(int i=1;i<=3;i++)
for(int j=1;j<=10;j++)
a[i][j]=-1;
dfs(1,1);
cout<<res<<endl;
}
参考博客:https://www.cnblogs.com/chiweiming/p/8992262.html 下一篇: WinForm 清空界面控件值的小技巧
推荐阅读
-
磁砖样式--第八阶蓝桥杯国赛第二题
-
[蓝桥杯决赛][2017年第八届真题]平方十位数(Java代码)
-
磁砖样式——第八届蓝桥杯C语言B组(国赛)第二题
-
2017第八届蓝桥杯决赛 磁砖样式
-
蓝桥杯 2018年决赛C/C++B组 #2 激光样式(动态规划、DFS)-- 酱懵静
-
蓝桥杯 2017年决赛C/C++B组 #4 发现环 (寻找回路、DFS)-- 酱懵静
-
第九届蓝桥杯大赛个人赛决赛(软件类)真题--C大学B组--激光样式题解(C语言)
-
磁砖样式--第八阶蓝桥杯国赛第二题
-
[蓝桥杯决赛][2017年第八届真题]平方十位数(Java代码)
-
[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc