第八届蓝桥杯决赛 磁砖样式（枚举）

标题：磁砖样式

小明家的一面装饰墙原来是 3*10 的小方格。
现在手头有一批刚好能盖住2个小方格的长方形瓷砖。
瓷砖只有两种颜色：黄色和橙色。

小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。
小明有个小小的强迫症：忍受不了任何$2\ast 2$的小格子是同一种颜色。
（瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝）
显然，对于 $2\ast 3$个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】

但对于$3\ast 10$ 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。
注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）

答案：101466

分析

• 对于这道题，我们只要枚举出所以的磁砖铺设情况，统计出满足要求的情况个数就能解出这道题了。但是怎么枚举，如何判断是否满足要求，如何记录当前满足条件的铺设情况。下面我们来解决这些问题：

枚举的方法
我们先规定一种铺设方式：先一行一行地铺，当这当前行铺满了，再去铺下一行。磁砖可以横向铺设，也可以竖向铺设，我们可以分开写成两个部分，根据当前行剩余的空位来选择横向铺设还是纵向铺设。对于各个位置状态的标记，如果没有铺设，该位置的状态值为-1；如果铺黄色，该位置的状态值为0；如果橙色，该位置的状态值为1。

判断是否满足要求
只要任意$2\ast 2$的小方格里面状态值的和不为0和4就可以判断为符合条件。

记录当前铺设情况
一共有30个位置，每个位置都只有两种状态（橙色或者黄色），我们可以用二进制来进行状态记录，然后把状态值放进一个集合中（集合中的元素不会重复），最后把集合的大小输出即可得到花样总数。

代码如下

import java.util.*;public class Main {final static int r=3,c=10;static int a[][]=new int [r][c];static Set<Integer> set=new HashSet<>();static boolean check() {for(int i=0;i<r-1;i++)for(int j=0;j<c-1;j++)if((a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1])%4==0)return false;return true;}static void dfs(int x,int y) {if(a[x][y]==-1) {//横向铺设if(y+1<c && a[x][y+1]==-1) {for(int i=0;i<2;i++) {a[x][y]=a[x][y+1]=i;if(y==c-1) {dfs(x+1, 0);}else {dfs(x, y+1);}a[x][y]=a[x][y+1]=-1;//backtracking}}//竖向铺设if(x+1<r && a[x+1][y]==-1) {for(int i=0;i<2;i++) {a[x][y]=a[x+1][y]=i;if(y==c-1) {dfs(x+1, 0);}else {dfs(x, y+1);}a[x][y]=a[x+1][y]=-1;//backtracking}}}else {if(y==c-1 && x==r-1) {if(check()) {int res=0;for(int i=0;i<r;i++)for(int j=0;j<c;j++) res=(res<<1)+a[i][j];set.add(res);}return;}//if there is still space leftif(y==c-1) {dfs(x+1, 0);}else {dfs(x, y+1);}}}public static void main(String[] args) {for(int i=0;i<r;i++)Arrays.fill(a[i], -1);dfs(0, 0);System.out.println(set.size());} }

总结

以上是生活随笔为你收集整理的第八届蓝桥杯决赛 磁砖样式（枚举）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。