Pku JudgeOnline

今日解いた問題はhttp://acm.pku.edu.cn/JudgeOnline/problem?id=2411

1×2のタイルでh×w(h,w<=11)の面を敷き詰める方法は何通りあるか?

再帰的に全探索する．ただし，h段目を埋めるときにはh-1段目のタイルの形状だけに注目すればよいので，メモ化が効いてmax(h,w)*(2^min(h,w))ぐらいの記憶領域を用いれば，TLEを出さずにすむ．

この方法は昨年のICPCの学科の練習会でコーチの人に教えられて，感心したのだが今日解いてないことに気付いて解いた．

ソースは以下の通り．
いちいちビットを配列に直しているのが非常にいけてない．

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int h = sc.nextInt();
			int w = sc.nextInt();
			if(h==0 && w==0)break;
			long memo[][] = new long[h][1<<w];
			for(int i=0;i<memo.length;i++){
				Arrays.fill(memo[i], -1);
			}
			System.out.println(f(w,memo.length-1,memo[0].length-1,memo));
		}
	}
	static void toArr(int val,int index,boolean arr[]){
		if(index==arr.length)return;
		arr[index] = (val%2==1);
		toArr(val/2,index+1,arr);
	}
	static long f(int width,int h,int pattern,long memo[][]){
		if(h<0){
			if(pattern==memo[0].length-1)return 1;
			return 0;
		}
		if(memo[h][pattern]>=0)return memo[h][pattern];
		long res = 0;
		boolean arr[] = new boolean[width];
		for(int p=0;p<memo[0].length;p++){
			// p : w1*h2の置き方
			//patternと重なる必要がある.
			if((pattern|p)!=pattern)continue;
			//p2 : w2*h1の置き方
			int p2 = pattern ^ p;
			toArr(p2,0,arr);
			boolean f = true;
			for(int i = 0;i<arr.length;i++){
				if(arr[i]){
					if(i+1==arr.length || (!arr[i+1])){
						f = false;
						break;
					}else{
						i++;
					}
				}
			}
			if(!f)continue;
			long v=f(width,h-1,(memo[0].length-1)^p,memo);
			res += v;
		}
		memo[h][pattern] = res;
		return res;
	}
}

追記：
配列に変換部分を消す，あと無駄に行数を減らしてみた．

import java.util.*;
public class Main {
	static long memo[][];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int h = sc.nextInt();
			int w = sc.nextInt();
			if(h==0 && w==0)break;
			memo = new long[h][1<<w];
			for(int i=0;i<memo.length;i++)Arrays.fill(memo[i], -1);
			System.out.println(f(h-1,(1<<w)-1));
		}
	}
	static long f(int h,int pattern){
		if(h<0)return pattern==memo[0].length-1?1:0;
		if(memo[h][pattern]>=0)return memo[h][pattern];
		memo[h][pattern] = 0;
		l:for(int p=0;p<memo[0].length;p++){
			if((pattern|p)!=pattern)continue;
			int p2 = pattern^p;
			for(int i=1;i<=memo[0].length;i*=2){
				if((i&p2)!=0){
					i *=2;
					if((i&p2)==0)continue l;
				}
			}
			memo[h][pattern] +=f(h-1,(memo[0].length-1)^p);
		}
		return memo[h][pattern];
	}
}