### Triominoes题号：161 难度： 70 中英对照

A triomino is a shape consisting of three squares joined via the edges. There are two basic forms:

If all possible orientations are taken into account there are six:

Any n by m grid for which nxm is divisible by 3 can be tiled with triominoes.
If we consider tilings that can be obtained by reflection or rotation from another tiling as different there are 41 ways a 2 by 9 grid can be tiled with triominoes:

In how many ways can a 9 by 12 grid be tiled in this way by triominoes?

### Code

public final class p161 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static final int N=12;
static final int M=9;
static long dp[][][]=new long[N+1][1<<M][1<<M];
static boolean get(int s,int pos){
return (s&(1<<pos))!=0;
}
static String to(int x){
String s=Integer.toBinaryString(x);
while(s.length()<M) s="0"+s;
return new StringBuffer(s).reverse().toString();
}
static void dfs(int pos,int s1,int s2,int s3,long add,int n){
if(pos<M){
if(get(s3,pos)){
if(!get(s1,pos)) ;
return;
}else{
// #  ***  **  **  **  **
// #  **   #    #  ##  ##
// #  ###  ##  ##  #    #
// 0   1   2   3   4    5
// 0
if(!get(s1,pos)){
if(get(s2,pos)) ;
else{
//	System.out.println("填入0");
}
return;
}
// 1
if(pos+2<M
&& get(s1,pos) && get(s1,pos+1) && get(s1,pos+2)
&& get(s2,pos) && get(s2,pos+1)
&& !get(s3,pos+1) && !get(s3,pos+2)){
//	System.out.println("填入1");
}
// 2
if(pos+1<M
&& get(s1,pos) && get(s1,pos+1)
&& !get(s2,pos)
&& !get(s3,pos+1)){
//	System.out.println("填入2");
}
// 3
if(pos+1<M
&& get(s1,pos) && get(s1,pos+1)
&& !get(s2,pos+1)
&& !get(s3,pos+1)){
//	System.out.println("填入3");
}
// 4
if(pos+1<M
&& get(s1,pos) && get(s1,pos+1)
&& !get(s2,pos) && !get(s2,pos+1)){
//	System.out.println("填入4");
}
// 5
if(pos-1>=0
&& get(s1,pos) && get(s1,pos-1)
&& !get(s2,pos) && !get(s2,pos-1)){
//	System.out.println("填入5");
}
// #  ***  **  **  **  **
// #  **   #    #  ##  ##
// #  ###  ##  ##  #    #
// 0   1   2   3   4    5
// 什么也不填
//	System.out.println("填入null");
}
}else{
if(((~s1)&((1<<M)-1))==0){
//	System.out.printf("\n%s (%d)\n%s (%d)\n%s (%d) +> %d =>%d\n",to(s1),n-2,to(s2),n-1,to(s3),n,add,dp[n][s2][s3]);
}
}
}

static public String run() {
dp[0][(1<<M)-1][(1<<M)-1]=1;
for(int i=1;i<=N;i++){
for(int s1=i<=2?((1<<M)-1):0;s1<(1<<M);s1++){
for(int s2=i==1?((1<<M)-1):0;s2<(1<<M);s2++){
dfs(0,s1,s2,0,dp[i-1][s1][s2],i);
}
}
}
return ""+dp[N][(1<<M)-1][(1<<M)-1];
}
}

20574308184277971
933ms