磁砖样式--第八阶蓝桥杯国赛第二题

原创

---

标题：磁砖样式

小明家的一面装饰墙原来是 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：任意一个方格在其相邻的（上/下/左/右）方格至少有一个相同的数码；

代码如下：

  1 #include<stdio.h>
  2 
  3 int arr[3][6]={0};
  4 int count=0;
  5 
  6 int Judge(){
  7     int i=0;
  8     int j=0;
  9     //条件1:偶数个0和1    
 10     int count_zero=0;    //存储0/1个数 
 11     int count_one=0;
 12     for(i=0;i<=2;i++){
 13         for(j=0;j<=5;j++){
 14             if(arr[i][j]==0){
 15                 count_zero++;
 16             }
 17                 else{
 18                     count_one++;
 19                 }
 20         }
 21     }
 22     if(count_zero%2!=0 || count_one%2!=0){
 23         return 0;
 24     }
 25     //条件2：2*2方格的数字都不相同
 26     int x=0;
 27     int y=0;
 28     for(x=0;x<=1;x++){    //循环至行数-1 
 29         for(y=0;y<=4;y++){    //循环至列数-1 
 30             int a=arr[x][y];
 31             int b=arr[x][y+1];
 32             int c=arr[x+1][y];
 33             int d=arr[x+1][y+1];
 34             if(a==b && a==c && a==d && b==c && b==d && c==d)
 35                 return 0;
 36         }
 37     }
 38     //条件3：每个数的相邻位置要有与其相同的数
 39     for(i=0;i<=2;i++){
 40         for(j=0;j<=5;j++){
 41             int value=arr[i][j];
 42             if(i-1>=0){    //上
 43                 if(value==arr[i-1][j]){
 44                     continue;
 45                 }
 46             } 
 47             if(i+1<=1){    //下 
 48                 if(value==arr[i+1][j]){
 49                     continue;
 50                 }        
 51             }
 52             if(j-1>=0){    //左 
 53                 if(value==arr[i][j-1]){
 54                     continue;
 55                 }
 56             } 
 57             if(j+1<=2){    //右
 58                 if(value==arr[i][j+1]){
 59                     continue;
 60                 }
 61                 else{    //没有相邻的数码 
 62                     return 0;
 63             }
 64             }
 65         }
 66     }
 67     return 1;
 68 }
 69 
 70 void Style(int i,int j){    //i行、j列
 71 
 72     if(i==2 && j==6){    //得到一种贴砖方式
 73     
 74         if(Judge()==1){
 75         /*
 76             int a=0;    //输出
 77             int b=0;
 78             for(a=0;a<=1;a++){
 79                 for(b=0;b<=2;b++){
 80                     printf("%d ",arr[a][b]);
 81                     if(b==2){
 82                         printf("\n");
 83                     }
 84                 }
 85             }
 86         */
 87         count++;
 88         }
 89     return;
 90     }
 91 
 92     if(j==6){
 93         i++;
 94         j=0;
 95     }
 96     int v=0;
 97     for(v=0;v<=1;v++){    //每个位置0-1循环
 98         arr[i][j]=v;
 99         Style(i,j+1);
100         arr[i][j]=0;    //回溯
101     }
102 }
103 
104 int main(){
105     Style(0,0);
106     printf("%d",count);
107     return 0;
108 }

只检验了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种贴法即可。

 1 #include<stdio.h>
 2 #define row 3
 3 #define rank 10
 4 
 5 int count=0;
 6 int arr[row+2][rank+2]={0};    //--------------① 
 7 
 8 int Judge(int x,int y){    //每一块砖的左上、右上、左下、右下四个2*2方格 
 9     if(arr[x][y]==arr[x-1][y] && arr[x][y]==arr[x-1][y-1] && arr[x][y]==arr[x][y-1]){    //左上
10         return 0;
11     } 
12     if(arr[x][y]==arr[x-1][y] && arr[x][y]==arr[x-1][y+1] && arr[x][y]==arr[x][y+1]){    //右上
13         return 0;
14     }
15     if(arr[x][y]==arr[x][y-1] && arr[x][y]==arr[x+1][y-1] && arr[x][y]==arr[x+1][y]){    //左下
16         return 0;
17     }
18     if(arr[x][y]==arr[x][y+1] && arr[x][y]==arr[x+1][y] && arr[x][y]==arr[x+1][y+1]){    //右下
19         return 0;
20     }
21     return 1;
22 }
23 
24 void dfs(int x,int y){
25     if(x==3 && y==11){
26         count++;
27         return;
28     }
29     if(y==11){
30         dfs(x+1,1);
31         return;
32     }
33     if(arr[x][y]==-1){    //4种铺法可以任意顺序 
34         if(arr[x][y+1]==-1){    //    横铺1
35             arr[x][y]=1;
36             arr[x][y+1]=1;
37             if(Judge(x,y)==1){
38                 dfs(x,y+1);
39             }
40             arr[x][y]=-1;
41             arr[x][y+1]=-1;
42         } 
43         if(arr[x+1][y]==-1){    //    竖铺2
44             arr[x][y]=2;
45             arr[x+1][y]=2;
46             if(Judge(x,y)==1){
47                 dfs(x,y+1);
48             }
49             arr[x][y]=-1;
50             arr[x+1][y]=-1; 
51         }
52         if(arr[x+1][y]==-1){    //    竖铺1
53             arr[x][y]=1;
54             arr[x+1][y]=1;
55             if(Judge(x,y)==1){
56                 dfs(x,y+1);
57             }
58             arr[x][y]=-1;
59             arr[x+1][y]=-1;
60         }
61         if(arr[x][y+1]==-1){    //    横铺2
62             arr[x][y]=2;
63             arr[x][y+1]=2;
64             if(Judge(x,y)==1){
65                 dfs(x,y+1);
66             }
67             arr[x][y]=-1;
68             arr[x][y+1]=-1;
69         }
70     }
71     
72     else{
73         dfs(x,y+1);
74     }
75 }
76 
77 int main(){
78     int i=0;
79     int j=0;
80     for(i=1;i<=3;i++){    //-------------② 
81         for(j=1;j<=10;j++){
82             arr[i][j]=-1;
83         }
84     }
85     dfs(1,1);
86     printf("%d",count);
87     return 0;
88 }

对代码中①/②的解释：

①：申请5*12的空间为方便对3*10的方格进行2*2的判断

②：只能对3*10的方格进行赋值，保证第0/4行、第0/11列（即外围一圈）的值和里面3*10的方格不同，具有很大的便利性（请大家慢慢体会）。

答案：114434