public class Solution {
public static int qiejuzhen(int length,int high)
{
/*
result陣列大小為1，用來放答案，當然，將result設為static int型別也是可以的
*/
if((length*high)%2!=0)return 0;
//初始化時result[0]==0;
int[]result=new int[1];
sub(new boolean[length][high],length*high,result,0);
return result[0];
}
/*
flag[][]用來標誌哪些位置已經被分配，哪些位置沒有被分配
left用來指代還有多少位置沒有被分配
本演演算法為了去重，規定每一行必須分配完才能繼續分配下一行
row代表的就是已經分配到第幾行了
*/
public static void sub(boolean [][]flag,int left,int[]result,int row)
{
//當未分配的位置為0時，答案加1
if(left==0)
{
result[0]++;
return;
}
/*
因為前面row-1行已經被分配完畢了，所以從第row行開始分配就
可以了
*/
for(int i=row;i<flag.length;i++)
{
for(int j=0;j<flag[0].length;j++)
{
if(flag[i][j]==true)continue;
if(i<flag.length&&j+1<flag[0].length&&flag[i][j+1]==false)
{
flag[i][j]=true;
flag[i][j+1]=true;
sub(flag,left-2,result,i);
flag[i][j]=false;
flag[i][j+1]=false;
}
if(i+1<flag.length&&j<flag[0].length&&flag[i+1][j]==false)
{
flag[i][j]=true;
flag[i+1][j]=true;
sub(flag,left-2,result,i);
flag[i][j]=false;
flag[i+1][j]=false;
}
/*
這裡的return解釋一下，在此處flag[i][j]==false,不符合每一行必須分配完才能分配下一行的規定，
因為接下來就算是j++，也不會再次為flag[i][j]進行分配
*/
return;
}
}
}
public static void main(String[] args) {
int length=3;
int high=4;
System.out.println(qiejuzhen(length,high));
}
}