poj 2411 java

//            0 表示補上一格的豎放 或着 表示橫放
//            當上一層為0時  下一層相應位置取0 表示橫放  是以 要連跳兩格，取1表示豎放
//            有可能會超出  int範圍    要用long
import java.util.Scanner;

public class POJ_2411 {

	static int h,w;
	static long dp[][];
	static int i,j;
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		while(true){
			h = scan.nextInt();
			w = scan.nextInt();
			if(h==0&&w==0)
				break;
			dp = new long[20][3000];
			
			if(h*w%2==1){
				System.out.println("0");
				continue;
			}
			
			dp[0][0] = 1;
			
			for(i=0;i<=h;i++){         //  i為0時 是表示初始化第一行   第一行并沒有 1<<w種情況  像101就是不行的
				for(j=0;j<(1<<w);j++){ //  是以 以0  開始 初始化  第1行dp[1][...];
					if(dp[i][j]!=0){
						dfs(1,0);
					}
				}
			}
			
			System.out.println(dp[h][0]);
			
		}

	}

	public static void dfs(int x, int s) {
		
		if(x == w + 1){
			dp[i+1][s] += dp[i][j];
		}else{
			if(((j>>(x-1))&1)==1)     
				dfs(x+1,s);
			else{
				if(x+1<=w&&((j>>x)&1)==0) //如果第x+1位 為1的話  就需要給上補0，是以不能橫放,而且位數 首先要夠
					dfs(x+2,s);
				dfs(x+1,s|(1<<(x-1)));
			}	
		}
		
	}

}