题目：为了让蓝桥杯竞赛更顺利的进行，主办方决定给竞赛的机房重新铺放瓷砖。机房可以看成一个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
和题目答案一致
发现解这些问题非常有趣，多多运用在实际项目中。