磁砖样式——第八届蓝桥杯C语言B组（国赛）第二题
原创
标题：磁砖样式
小明家的一面装饰墙原来是 3*10 的小方格。
现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色：黄色和橙色。
小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。
小明有个小小的强迫症：忍受不了任何2*2的小格子是同一种颜色。
（瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝）
显然，对于 2*3 个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】
但对于 3*10 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。
注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）
一开始的想法是在数组里面枚举出全部的情况组合，比如2*3的方格，用0/1代表两种颜色；
那么一共会有pow（2,6）=64种情况，然后用3个判断条件筛选出符合要求的贴砖方式：
1: 数码0/1有偶数个；
2：任意2*2的方格的数码不能相同；
3：任意一个方格在其相邻的（上/下/左/右）方格至少有一个相同的数码；
代码如下：
#include<stdio.h>
int arr[][]={};
int count=;
int Judge(){
int i=;
int j=;
//条件1:偶数个0和1
int count_zero=; //存储0/1个数
int count_one=;
for(i=;i<=;i++){
for(j=;j<=;j++){
if(arr[i][j]==){
count_zero++;
}
else{
count_one++;
}
}
}
if(count_zero%!= || count_one%!=){
return ;
}
//条件2：2*2方格的数字都不相同
int x=;
int y=;
for(x=;x<=;x++){ //循环至行数-1
for(y=;y<=;y++){ //循环至列数-1
int a=arr[x][y];
int b=arr[x][y+];
int c=arr[x+][y];
int d=arr[x+][y+];
if(a==b && a==c && a==d && b==c && b==d && c==d)
return ;
}
}
//条件3：每个数的相邻位置要有与其相同的数
for(i=;i<=;i++){
for(j=;j<=;j++){
int value=arr[i][j];
if(i->=){ //上
if(value==arr[i-][j]){
continue;
}
}
if(i+<=){ //下
if(value==arr[i+][j]){
continue;
}
}
if(j->=){ //左
if(value==arr[i][j-]){
continue;
}
}
if(j+<=){ //右
if(value==arr[i][j+]){
continue;
}
else{ //没有相邻的数码
return ;
}
}
}
}
return ;
}
void Style(int i,int j){ //i行、j列
if(i== && j==){ //得到一种贴砖方式
if(Judge()==){
/*
int a=0; //输出
int b=0;
for(a=0;a<=1;a++){
for(b=0;b<=2;b++){
printf("%d ",arr[a][b]);
if(b==2){
printf("\n");
}
}
}
*/
count++;
}
return;
}
if(j==){
i++;
j=;
}
int v=;
for(v=;v<=;v++){ //每个位置0-1循环
arr[i][j]=v;
Style(i,j+);
arr[i][j]=; //回溯
}
}
int main(){
Style(,);
printf("%d",count);
return ;
}
只检验了2*3、3*6的方格的样例，2*3的样例输出了正确的答案，3*6的输出错误。
3*10的数据量太大跑不出来了。
上面的3个控制条件太少，像
1 0 1 1 0 0
1 1 0 0 0 1
1 0 1 1 0 1
这样的贴砖方式能通过条件但却是不符合要求的，因为这种方式太过于暴力，所以没有继续改进。
此题应该通过DFS解决：
3*10的方格，每个空方格都可以有4种贴法：（我们以1/2号定义两种颜色的砖）
横着贴1号砖、横着贴2号砖、竖着贴1号砖、竖着贴2号砖
所以我们用DFS搜索每块空砖的这4种贴法即可。
#include<stdio.h>
#define row 3
#define rank 10 int count=;
int arr[row+][rank+]={}; //--------------① int Judge(int x,int y){ //每一块砖的左上、右上、左下、右下四个2*2方格
if(arr[x][y]==arr[x-][y] && arr[x][y]==arr[x-][y-] && arr[x][y]==arr[x][y-]){ //左上
return ;
}
if(arr[x][y]==arr[x-][y] && arr[x][y]==arr[x-][y+] && arr[x][y]==arr[x][y+]){ //右上
return ;
}
if(arr[x][y]==arr[x][y-] && arr[x][y]==arr[x+][y-] && arr[x][y]==arr[x+][y]){ //左下
return ;
}
if(arr[x][y]==arr[x][y+] && arr[x][y]==arr[x+][y] && arr[x][y]==arr[x+][y+]){ //右下
return ;
}
return ;
} void dfs(int x,int y){
if(x== && y==){
count++;
return;
}
if(y==){
dfs(x+,);
return;
}
if(arr[x][y]==-){ //4种铺法可以任意顺序
if(arr[x][y+]==-){ // 横铺1
arr[x][y]=;
arr[x][y+]=;
if(Judge(x,y)==){
dfs(x,y+);
}
arr[x][y]=-;
arr[x][y+]=-;
}
if(arr[x+][y]==-){ // 竖铺2
arr[x][y]=;
arr[x+][y]=;
if(Judge(x,y)==){
dfs(x,y+);
}
arr[x][y]=-;
arr[x+][y]=-;
}
if(arr[x+][y]==-){ // 竖铺1
arr[x][y]=;
arr[x+][y]=;
if(Judge(x,y)==){
dfs(x,y+);
}
arr[x][y]=-;
arr[x+][y]=-;
}
if(arr[x][y+]==-){ // 横铺2
arr[x][y]=;
arr[x][y+]=;
if(Judge(x,y)==){
dfs(x,y+);
}
arr[x][y]=-;
arr[x][y+]=-;
}
} else{
dfs(x,y+);
}
} int main(){
int i=;
int j=;
for(i=;i<=;i++){ //-------------②
for(j=;j<=;j++){
arr[i][j]=-;
}
}
dfs(,);
printf("%d",count);
return ;
}
对代码中①/②的解释：
①：申请5*12的空间为方便对3*10的方格进行2*2的判断
②：只能对3*10的方格进行赋值，保证第0/4行、第0/11列（即外围一圈）的值和里面3*10的方格不同，具有很大的便利性（请大家慢慢体会）。
答案：114434
3:38:00
2018-05-07
最新文章
- Time Consume Problem
- Android课程---关于Service的学习(后台运行)
- Ubuntu install g++
- Linux echo, sort, sed 等一些命令总结
- Git使用日记
- python_操作oracle数据库
- 2016年11月27日 星期日 --出埃及记 Exodus 20:18
- [国嵌攻略][171][V4L2图像编程接口深度学习]
- java 里面保留字volatile及其与synchronized的区别
- Linux Debugging（四）: 使用GDB来理解C++ 对象的内存布局（多重继承，虚继承）
- Android Studio集成Genymotion
- 【从零开始搭建自己的.NET Core Api框架】（二）搭建项目的整体架构
- python 1-100的数相加的和
- Dubbo 源码分析 - 自适应拓展原理
- socket关闭状态问题
- 【ASP.NET Core】从向 Web API 提交纯文本内容谈起
- Echo团队Alpha冲刺随笔集合
- JAVA线程sleep与wait区别
- xgboost gbdt特征点分烈点
- Python学习---Model拾遗[1]180318