PKU 2411-Mondriaan's Dream

問題概要

WxHのマスに1x2のタイルを敷き詰める場合の数を求めよ

解法

2^w個のデーターを保持しつつメモ化再帰

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Scanner input;
	long [][][]dp;
	int W,H,MASK;
	long dfs(int bit,int x,int y){
		if(x==W)return dfs(bit,0,y+1);
		if(y==H&&bit==0)return 1;
		if(y==H)return 0;
		if(dp[x][y][bit]>=0)return dp[x][y][bit];
		long res=0;
		if((bit&1)==1){//既に何かおかれている
			res+=dfs((bit>>1),x+1,y);
		}else{

			//横における
			if(x<W-1&&((bit>>1)&1)==0){
				res+=dfs((bit>>2),x+2,y);
			}
			//縦には絶対における
			res+=dfs((bit>>1)|(1<<(W-1)),x+1,y);
		}
		return dp[x][y][bit]=res;
	}
	long solve(int W_,int H_){
		W=W_;H=H_;
		MASK=(1<<W)-1;

		if(W*H%2==1)return 0;
		dp=new long[11][11][1<<11];
		for(int y=0;y<H;y++){
			for(int x=0;x<W;x++){
				for(int k=0;k<1<<W;k++){
					dp[x][y][k]=-1;
				}
			}
		}
		return dfs(0,0,0);
	}
	void run(){
		input=new Scanner(System.in);
		int W,H;
		while(true){
			W=input.nextInt();H=input.nextInt();
			if(W==0)break;
			printf("%d\n",solve(W,H));
		}
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}