当前位置:首页 » Project Euler » 详细页

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?


Solution

状态压缩的动态规划以及深度优先搜索。 填充第i行时,只会影响前两行的状态,记录dp[i][j][k]表示现在填充第i行,第i-2行的状态为j,第i-1行的状态为k,状态用二进制表示。 根据第i-2行和第i-1行的状态可以使用深度优先搜索,枚举所有可能填入的积木情况,将填充后的第i-1行的状态si_1和第i行的状态s更新dp[i+1][si_1][s]即可。 需要注意,深度优先搜索时需要考虑什么也不填入的情况,同时有一个剪枝是填第i行时要保证第i-2行完全填充,否则总会缺一个的。 初始状态可以考虑棋盘范围外的所有点都是有方块填充的。

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){
	//	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,pos,add);
		if(pos<M){
			if(get(s3,pos)){
				if(!get(s1,pos)) ;
				else dfs(pos+1,s1,s2,s3,add,n);
				return;
			}else{
				// #  ***  **  **  **  **
				// #  **   #    #  ##  ## 
				// #  ###  ##  ##  #    #
				// 0   1   2   3   4    5
				// 0
				if(!get(s1,pos)){
					if(get(s2,pos)) ;
					else{
					//	System.out.println("填入0");
						dfs(pos+1,s1|(1<<pos),s2|(1<<pos),s3|(1<<pos),add,n);
					}
					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");
					dfs(pos+3,s1,s2,s3|(7<<(pos)),add,n);
				}
				// 2
				if(pos+1<M
						&& get(s1,pos) && get(s1,pos+1)
						&& !get(s2,pos) 
						&& !get(s3,pos+1)){
				//	System.out.println("填入2");
					dfs(pos+2,s1,s2|(1<<pos),s3|(3<<(pos)),add,n);
				}
				// 3
				if(pos+1<M
						&& get(s1,pos) && get(s1,pos+1)
						&& !get(s2,pos+1)
						&& !get(s3,pos+1)){
				//	System.out.println("填入3");
					dfs(pos+2,s1,s2|(1<<(pos+1)),s3|(3<<(pos)),add,n);
				}
				// 4
				if(pos+1<M
						&& get(s1,pos) && get(s1,pos+1)
						&& !get(s2,pos) && !get(s2,pos+1)){
				//	System.out.println("填入4");
					dfs(pos+1,s1,s2|(3<<(pos)),s3|(1<<pos),add,n);
				}
				// 5
				if(pos-1>=0
						&& get(s1,pos) && get(s1,pos-1)
						&& !get(s2,pos) && !get(s2,pos-1)){
				//	System.out.println("填入5");
					dfs(pos+1,s1,s2|(3<<(pos-1)),s3|(1<<pos),add,n);
				}
				// #  ***  **  **  **  **
				// #  **   #    #  ##  ## 
				// #  ###  ##  ##  #    #
				// 0   1   2   3   4    5
				// 什么也不填
			//	System.out.println("填入null");
				dfs(pos+1,s1,s2,s3,add,n);
			}
		}else{
			if(((~s1)&((1<<M)-1))==0){
				dp[n][s2][s3]+=add;
			//	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