题目：为了让蓝桥杯竞赛更顺利的进行，主办方决定给竞赛的机房重新铺放瓷砖。机房可以看成一个n*m的矩形，而这次使用的瓷砖比较特别，有两种形状，如【图1.png】所示。在铺放瓷砖时，可以旋转。

主办方想知道，如果使用这两种瓷砖把机房铺满，有多少种方案。

【输入格式】

输入的第一行包含两个整数，分别表示机房两个方向的长度。

【输出格式】

输出一个整数，表示可行的方案数。这个数可能很大，请输出这个数除以65521的余数。

【样例输入1】

4 4

【样例输出1】

2

【样例说明1】

这两种方案如下【图2.png】所示：

【样例输入2】

2 6

【样例输出2】

4

【数据规模与约定】

对于20%的数据，1<=n, m<=5。

对于50%的数据，1<=n<=100，1<=m<=5。

对于100%的数据，1<=n<=10^15，1<=m<=6。

资源约定：

峰值内存消耗（含虚拟机） < 512M

CPU消耗 < 8000ms

解答：

这道题我想了三天，最终想到的解题思路如下。

一个矩形要铺满两种图形的瓷砖，瓷砖形状不相同，每个瓷砖可以上下左右翻转拼出来花样是不一样的。先看有多少种铺发，再做去重。

有多少种铺发：有一个二维数组表示方格，已经放入的瓷砖所占的格子用标记记录表明已经占用，不能在放，L形瓷砖可以上下左右翻转共有四种摆放方式，摆放方式不一样不能可能重复，但是同一种摆放方式有可能会重复，所以需要在放入格子中也要记录当时放入的方式。T形瓷砖一样有上下左右四种摆放方式，为每种方式做一个标记放入占用的二维数组中。铺砖采用扫描格子的方法从上到下，从左到右逐个格子判断，如果是空格子根据瓷砖的摆放方式逐个尝试，如果能摆下，就在一个二维数组中记录摆放的瓷砖标记和方式标记，等扫描到最后一个格子后。判断这个二维数组是否每个格式都不为空，都是被占用的则判断为铺满了，可以记录一个结果放入到一个List中。

做去重：在第一步获取到的铺满的List的二维数组中，把二维数组拉伸拼成一个数组，在拼成一个字符串。就得到一个List的字符串对象。用for循环排除其中相同的字符串，最后得到可以铺设的方法。

代码：

public class PuZhuan { public static void main(String[] args) { System.out.println("PZ-complix 2-3:" + puzhuan(2, 3)); System.out.println("PZ-complix 4-4:" + puzhuan(4, 4)); System.out.println("PZ-complix 2-6:" + puzhuan(2, 6)); } static int n=0;static int puzhuan(int x,int y){n=0; String[][] gezi = new String[x][y];for(int i=0;i<gezi.length;i++) Arrays.fill(d[i],"0"); //初始化设置为0 dopuzhuan(x,y,gezi,0,"");//x是行数，y是列数，gezi是二维数组记录标记用，0是开始从第0个位置开始扫描格式，空字符串是记录已经标记的格子return n%65521; } //下面代码长了点感觉可以优化，大多是判断当前格子在瓷砖的位子和翻转的情况 static void dopuzhuan(int r,int c,String[][] d,int p,String s){if(isfull(d)){ //如果满格铺设 String[] ss = s.split(",");//当前已经标记的格子信息if(!isSame(tm,ss)) {//和之前满足条件的铺发比较是否相同n++; //如果不相同计数 //print(d);tm.add(Arrays.asList(ss)); //放入列表中 }return; }if(p>=r*c)return; //当前点大于格子数退出int cr =p/c; //当前所在的行编号，从0开始int cc = p%c; //当前所在的列编号，从0开始if(d[cr][cc].equals("0") && cr>=0 && cr<r && cc>=0 && cc<c){ //满足不超出格子的坐标条件//当前格子可能所在L的位子，L有三个格子组成，且有上下左右四种翻转方式，所以当前格子可能处于4*3=12种可能的位置if((cr>0 && cc<c-1 && d[cr][cc+1].equals("0") && d[cr-1][cc+1].equals("0") )){ d[cr][cc]="1";d[cr][cc+1]="1";d[cr-1][cc+1]="1";//标记这些格子已经占用dopuzhuan(r,c,d,p+2,s+","+d(new int[][]{{cr,cc},{cr,cc+1},{cr-1,cc+1}},"_|"));//继续往下个点铺设，“_|”表示L形瓷砖的一种翻转方式 d[cr][cc]="0";d[cr][cc+1]="0";d[cr-1][cc+1]="0"; } //L形第2种可能位置if(cr>0 && cc>0 && d[cr][cc-1].equals("0") && d[cr-1][cc].equals("0") ){ d[cr][cc]="1";d[cr][cc-1]="1";d[cr-1][cc]="1";dopuzhuan(r,c,d,p+1,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr-1,cc}},"_|")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr-1][cc]="0"; } //L形第3种可能位置if((cr>=0 && cr<r-1 && cc>0 && d[cr+1][cc].equals("0") && d[cr+1][cc-1].equals("0") )){ d[cr][cc]="1";d[cr+1][cc]="1";d[cr+1][cc-1]="1";dopuzhuan(r,c,d,p+1,s+","+d(new int[][]{{cr,cc},{cr+1,cc},{cr+1,cc-1}},"_|")); d[cr][cc]="0";d[cr+1][cc]="0";d[cr+1][cc-1]="0"; } //L形第4种可能位置if((cr>=0 && cr<r-1 && cc>=0 && cc<c-1 && d[cr+1][cc].equals("0") && d[cr+1][cc+1].equals("0") )){ d[cr][cc]="1";d[cr+1][cc]="1";d[cr+1][cc+1]="1";dopuzhuan(r,c,d,p+2,s+","+d(new int[][]{{cr,cc},{cr+1,cc},{cr+1,cc+1}},"|_")); d[cr][cc]="0";d[cr+1][cc]="0";d[cr+1][cc+1]="0"; }//L形第5种可能位置if((cr>0 && cc<c-1 && cc>=0 && d[cr-1][cc].equals("0") && d[cr][cc+1].equals("0") )){ d[cr][cc]="1";d[cr-1][cc]="1";d[cr][cc+1]="1";dopuzhuan(r,c,d,p+2,s+","+d(new int[][]{{cr,cc},{cr-1,cc},{cr,cc+1}},"|_")); d[cr][cc]="0";d[cr-1][cc]="0";d[cr][cc+1]="0"; }//L形第6种可能位置if((cr>0 && cc>0 && d[cr][cc-1].equals("0") && d[cr-1][cc-1].equals("0") )){ d[cr][cc]="1";d[cr][cc-1]="1";d[cr-1][cc-1]="1";dopuzhuan(r,c,d,p+1,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr-1,cc-1}},"|_")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr-1][cc-1]="0"; }//L形第7种可能位置if((cr>=0 && cr<r-1 && cc>=0 && cc<c-1 && d[cr][cc+1].equals("0") && d[cr+1][cc+1].equals("0") )){ d[cr][cc]="1";d[cr][cc+1]="1";d[cr+1][cc+1]="1";dopuzhuan(r,c,d,p+2,s+","+d(new int[][]{{cr,cc},{cr,cc+1},{cr+1,cc+1}},"'|")); d[cr][cc]="0";d[cr][cc+1]="0";d[cr+1][cc+1]="0"; }//L形第8种可能位置if((cr>=0 && cr<r-1 && cc>0 && d[cr][cc-1].equals("0") && d[cr+1][cc].equals("0") )){ d[cr][cc]="1";d[cr][cc-1]="1";d[cr+1][cc]="1";dopuzhuan(r,c,copy(d),p+1,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr+1,cc}},"'|")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr+1][cc]="0"; }//L形第9种可能位置if((cr>0 && cc>0 && d[cr-1][cc].equals("0") && d[cr-1][cc-1].equals("0") )){ d[cr][cc]="1";d[cr-1][cc]="1";d[cr-1][cc-1]="1";dopuzhuan(r,c,d,p+1,s+","+d(new int[][]{{cr,cc},{cr-1,cc},{cr-1,cc-1}},"'|")); d[cr][cc]="0";d[cr-1][cc]="0";d[cr-1][cc-1]="0"; }//L形第10种可能位置if((cr>=0 && cr<r-1 && cc>=0 && cc<c-1 && d[cr][cc+1].equals("0") && d[cr+1][cc].equals("0") )){ d[cr][cc]="1";d[cr][cc+1]="1";d[cr+1][cc]="1";dopuzhuan(r,c,d,p+2,s+","+d(new int[][]{{cr,cc},{cr,cc+1},{cr+1,cc}},"|'")); d[cr][cc]="0";d[cr][cc+1]="0";d[cr+1][cc]="0"; }//L形第11种可能位置if((cr>=0 && cr<r-1 && cc>1 && d[cr][cc-1].equals("0") && d[cr+1][cc-1].equals("0") )){ d[cr][cc]="1";d[cr][cc-1]="1";d[cr+1][cc-1]="1";dopuzhuan(r,c,d,p+1,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr+1,cc-1}},"|'")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr+1][cc-1]="0"; }//L形第12种可能位置if((cr>0 && cc<c-1 && cc>=0 && d[cr-1][cc].equals("0") && d[cr-1][cc+1].equals("0") )){ d[cr][cc]="1";d[cr-1][cc]="1";d[cr-1][cc+1]="1";dopuzhuan(r,c,d,p+2,s+","+d(new int[][]{{cr,cc},{cr-1,cc},{cr-1,cc+1}},"|'")); d[cr][cc]="0";d[cr-1][cc]="0";d[cr-1][cc+1]="0"; }//放T的情况，T形的位置可能有4*4=16中位置情况if(cr>=0 && cr<r-1 && cc>=0 && cc<c-2 && d[cr][cc+1].equals("0") && d[cr][cc+2].equals("0") && d[cr+1][cc+1].equals("0")){ d[cr][cc]="2";d[cr][cc+1]="2";d[cr][cc+2]="2";d[cr+1][cc+1]="2";dopuzhuan(r,c,d,p+3,s+","+d(new int[][]{{cr,cc},{cr,cc+1},{cr,cc+2},{cr+1,cc+1}},"'|'")); d[cr][cc]="0";d[cr][cc+1]="0";d[cr][cc+2]="0";d[cr+1][cc+1]="0"; }//T第2种情况if(cr>=0 && cr<r-1 && cc>0 && cc<r-1 && d[cr][cc-1].equals("0") && d[cr][cc+1].equals("0") && d[cr+1][cc].equals("0")){ d[cr][cc]=""+2;d[cr][cc-1]=""+2;d[cr][cc+1]=""+2;d[cr+1][cc]=""+2;dopuzhuan(r,c,d,p+2,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr,cc+1},{cr+1,cc}},"'|'")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr][cc+1]="0";d[cr+1][cc]="0"; }//T第3种情况if(cr>=0 && cr<r-1 && cc>1 && d[cr][cc-2].equals("0") && d[cr][cc-1].equals("0") && d[cr+1][cc-1].equals("0")){ d[cr][cc]=""+2;d[cr][cc-2]=""+2;d[cr][cc-1]=""+2;d[cr+1][cc-1]=""+2;dopuzhuan(r,c,copy(d),p+1,s+","+d(new int[][]{{cr,cc},{cr,cc-2},{cr,cc-1},{cr+1,cc-1}},"'|'")); d[cr][cc]="0";d[cr][cc-2]="0";d[cr][cc-1]="0";d[cr+1][cc-1]="0"; }//T第4种情况if(cr>0 && cc>0 && cc<c-1 && d[cr-1][cc].equals("0") && d[cr-1][cc-1].equals("0") && d[cr-1][cc+1].equals("0")){ d[cr][cc]=""+2;d[cr-1][cc]=""+2;d[cr-1][cc-1]=""+2;d[cr-1][cc+1]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr-1,cc},{cr-1,cc-1},{cr-1,cc+1}},"'|'")); d[cr][cc]="0";d[cr-1][cc]="0";d[cr-1][cc-1]="0";d[cr-1][cc+1]="0"; }//T第5种情况if(cr>0 && cc>=0 && cc<c-2 && d[cr][cc+1].equals("0") && d[cr][cc+2].equals("0") && d[cr-1][cc+1].equals("0")){ d[cr][cc]=""+2;d[cr][cc+1]=""+2;d[cr][cc+2]=""+2;d[cr-1][cc+1]=""+2;dopuzhuan(r,c,copy(d),p+3,s+","+d(new int[][]{{cr,cc},{cr,cc+1},{cr,cc+2},{cr-1,cc+1}},".|.")); d[cr][cc]="0";d[cr][cc+1]="0";d[cr][cc+2]="0";d[cr-1][cc+1]="0"; }//T第6种情况if(cr>0 && cc<c-1 && cc>0 && d[cr][cc-1].equals("0") && d[cr][cc+1].equals("0") && d[cr-1][cc].equals("0")){ d[cr][cc]=""+2;d[cr][cc-1]=""+2;d[cr][cc+1]=""+2;d[cr-1][cc]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr,cc+1},{cr-1,cc}},".|.")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr][cc+1]="0";d[cr-1][cc]="0"; }//T第7种情况if(cr>0 && cc>1 && d[cr][cc-2].equals("0") && d[cr][cc-1].equals("0") && d[cr-1][cc-1].equals("0")){ d[cr][cc]=""+2;d[cr][cc-2]=""+2;d[cr][cc-1]=""+2;d[cr-1][cc-1]=""+2;dopuzhuan(r,c,copy(d),p+1,s+","+d(new int[][]{{cr,cc},{cr,cc-2},{cr,cc-1},{cr-1,cc-1}},".|.")); d[cr][cc]="0";d[cr][cc-2]="0";d[cr][cc-1]="0";d[cr-1][cc-1]="0"; }//T第8种情况if(cr>=0 && cr<r-1 && cc>1 &&cc<c-1 && d[cr+1][cc].equals("0") && d[cr+1][cc-1].equals("0") && d[cr+1][cc+1].equals("0")){ d[cr][cc]=""+2;d[cr+1][cc]=""+2;d[cr+1][cc-1]=""+2;d[cr+1][cc+1]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr+1,cc},{cr+1,cc-1},{cr+1,cc+1}},".|.")); d[cr][cc]="0";d[cr+1][cc]="0";d[cr+1][cc-1]="0";d[cr+1][cc+1]="0"; }//T第9种情况if(cr>0 && cr<r-1 && cc>=0 && cc<c-1 && d[cr][cc+1].equals("0") && d[cr-1][cc+1].equals("0") && d[cr+1][cc+1].equals("0")){ d[cr][cc]=""+2;d[cr][cc+1]=""+2;d[cr-1][cc+1]=""+2;d[cr+1][cc+1]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr,cc+1},{cr-1,cc+1},{cr+1,cc+1}},"-|")); d[cr][cc]="0";d[cr][cc+1]="0";d[cr-1][cc+1]="0";d[cr+1][cc+1]="0"; }//T第10种情况if(cr>0 && cr<r-1 && cc>0 && d[cr][cc-1].equals("0") && d[cr-1][cc].equals("0") && d[cr+1][cc].equals("0")){ d[cr][cc]=""+2;d[cr][cc-1]=""+2;d[cr-1][cc]=""+2;d[cr+1][cc]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr-1,cc},{cr+1,cc}},"-|")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr-1][cc]="0";d[cr+1][cc]="0"; }//T第11种情况if(cr>=0 && cr<r-2 && cc>0 && d[cr+1][cc].equals("0") && d[cr+2][cc].equals("0") && d[cr+1][cc-1].equals("0")){ d[cr][cc]=""+2;d[cr+1][cc]=""+2;d[cr+2][cc]=""+2;d[cr+1][cc-1]=""+2;dopuzhuan(r,c,copy(d),p+1,s+","+d(new int[][]{{cr,cc},{cr+1,cc},{cr+2,cc},{cr+1,cc-1}},"-|")); d[cr][cc]="0";d[cr+1][cc]="0";d[cr+2][cc]="0";d[cr+1][cc-1]="0"; }//T第12种情况if(cr>1 && cc>0 && d[cr-1][cc].equals("0") && d[cr-2][cc].equals("0") && d[cr-1][cc-1].equals("0")){ d[cr][cc]=""+2;d[cr-1][cc]=""+2;d[cr-2][cc]=""+2;d[cr-1][cc-1]=""+2;dopuzhuan(r,c,copy(d),p+1,s+","+d(new int[][]{{cr,cc},{cr-1,cc},{cr-2,cc},{cr-1,cc-1}},"-|")); d[cr][cc]="0";d[cr-1][cc]="0";d[cr-2][cc]="0";d[cr-1][cc-1]="0"; }//T第13种情况if(cr>=0 && cr<r-2 && cc>=0 && cc<c-1 && d[cr+1][cc].equals("0") && d[cr+2][cc].equals("0") && d[cr+1][cc+1].equals("0")){ d[cr][cc]=""+2;d[cr+1][cc]=""+2;d[cr+2][cc]=""+2;d[cr+1][cc+1]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr+1,cc},{cr+2,cc},{cr+1,cc+1}},"|-")); d[cr][cc]="0";d[cr+1][cc]="0";d[cr+2][cc]="0";d[cr+1][cc+1]="0"; }//T第14种情况if(cr>0 && cr<r-1 && cc>=0 && cc<c-1 && d[cr-1][cc].equals("0") && d[cr+1][cc].equals("0") && d[cr][cc+1].equals("0")){ d[cr][cc]=""+2;d[cr-1][cc]=""+2;d[cr+1][cc]=""+2;d[cr][cc+1]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr-1,cc},{cr+1,cc},{cr,cc+1}},"|-")); d[cr][cc]="0";d[cr-1][cc]="0";d[cr+1][cc]="0";d[cr][cc+1]="0"; }//T第15种情况if(cr>1 && cr<r && cc>=0 && cc<c-1 && d[cr-1][cc].equals("0") && d[cr-2][cc].equals("0") && d[cr-1][cc+1].equals("0")){ d[cr][cc]=""+2;d[cr-1][cc]=""+2;d[cr-2][cc]=""+2;d[cr-1][cc+1]=""+2;dopuzhuan(r,c,copy(d),p+2,s+","+d(new int[][]{{cr,cc},{cr-1,cc},{cr-2,cc},{cr-1,cc+1}},"|-")); d[cr][cc]="0";d[cr-1][cc]="0";d[cr-2][cc]="0";d[cr-1][cc+1]="0"; }//T第16种情况if(cr>0 && cr<r-1 && cc>0 && d[cr][cc-1].equals("0") && d[cr-1][cc-1].equals("0") && d[cr+1][cc-1].equals("0")){ d[cr][cc]=""+2;d[cr][cc-1]=""+2;d[cr-1][cc-1]=""+2;d[cr+1][cc-1]=""+2;dopuzhuan(r,c,copy(d),p+1,s+","+d(new int[][]{{cr,cc},{cr,cc-1},{cr-1,cc-1},{cr+1,cc-1}},"|-")); d[cr][cc]="0";d[cr][cc-1]="0";d[cr-1][cc-1]="0";d[cr+1][cc-1]="0"; }pingz(r,c,d,p+1,s);//如果没有满足的，继续向前推进一格 } } //是否是满格铺设的，没有一个格子等于0就是满格铺设static boolean isfull(String[][] a){for(int i=0;i<a.length;i++){for(int j=0;j<a[i].length;j++){if(a[i][j].equals("0")) return false; } }return true; } //判断满格铺设方法是否相同，一个格子中的标记用一个字符串表示，一个字符数组就表示满格中每个格点上的总标记，字符串中包含格子坐标，瓷砖类型，瓷砖上下左右翻转方式等信息。static boolean isSame(List<List> s,String[] ss){if(s.size()==0)return false;for(List t:s){boolean b= true;for(String st:ss) {if (!t.contains(st)){ b= false;break; } }if(b){return true; } }return false; } //当前瓷砖占用的格子标记为一个字符串，每个格子标记用“，”分割，格子标记为rowNum+"."+colNum+瓷砖和翻转方式标记static String d(int[][] d,String c){ StringBuffer sb = new StringBuffer();for(int i=0;i<d.length;i++){if(i>0)sb.append(","); sb.append(d[i][0]).append(".").append(d[i][1]).append(c); }return sb.toString(); }}

运行结果

PZ-complix 2-3:2

PZ-complix 4-4:2

PZ-complix 2-6:4

和题目答案一致

发现解这些问题非常有趣，多多运用在实际项目中。