POJ 2411 Mondriaan's Dream

ドミノ敷き詰め問題。
完全マッチングの個数を数える問題ともいうのかな。
bitDPでときました。

#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
int w,h;
long long  int dp[2][1 << 11];
int main(){
	while(1){
		scanf("%d%d",&h,&w);
		if(h == 0 && w == 0)break;
		memset(dp,0,sizeof(dp));
		long long int *crt = dp[0], *next = dp[1];
		crt[0] = 1;
		for(int i = h - 1;i >= 0;i--){
			for(int j = w - 1;j >= 0;j--){
				for(int used = 0;used < 1 << w;used++){
					if(used >> j & 1){
						next[used] = crt[used & ~(1 << j)];
					}else{
						long long int res = 0;
						if(j + 1 < w && !(used >> (j+1) & 1)){
							res += crt[used | 1 << (j+1)];
						}
						if(i + 1 < h){
							res += crt[used | 1 << j];
						}
						next[used] = res;
					}
				}
				swap(crt,next);
			}
		}
		printf("%lld\n",crt[0]);
	}
	return 0;
}