完全覆盖 II 之状态压缩

3/8/2017来源:ASP.NET技巧人气:1717

完全覆盖 II

时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述 有一天acmj在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉把棋盘完全覆盖有点简单,他想能不能把完全覆盖的种数求出来?由于游戏难度增加他自己已经没法解决了,于是他希望大家能用程序来帮他把问题解决了。 输入有多组数据。 每组数据占一行,有两个正整数n(0<n<12),m(0<m<12)。 当n,m等于0时输入结束输出每组数据输出占一行,输出完全覆盖的种数。样例输入
2 2
2 3
2 4
2 11
4 11
0 0
样例输出
2
3
5
144
51205
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long a[15][15];
long long dp[15][1<<12];
int n,m;
bool judge1(int s){//判断的标准是必须连续两格为1 
	int i;
	for(i=1;i<=m;){
		if(s & (1<<i-1)){
			if(i==m)return 0;
			else if(s & (1<<(i)))i+=2;
			else return 0;
		}
		else i++;
	}
	return 1;
}
bool judge2(int s,int ss){//判断第i-1行的s情况与i行的情况是否兼容 
	int i;
	for(i=1;i<=m;){
		if(s & (1<<i-1)){
			if(ss & (1<<i-1)){ 
				if(i==m ||!(s &(1<<i))||!(ss &(1<<i)))return 0;
				else i+=2;
			}
			else i++;
		}
		else{
			if(ss &(1<<i-1))i++;
			else return 0;
		}
	}
	return 1;
}
void solve(){
	int s,ss,i;
	memset(dp,0,sizeof(dp));
	if(n<m){//为了减少情况数量,使小的为列数 
		int temp;
		temp=n;n=m;m=temp;
	}
	int maxx=(1<<m)-1;
	for(s=0;s<=maxx;s++){//第一行每一种可行的情况 
		if(judge1(s)){ 
			dp[1][s]=1;
		}
	}
	for(i=2;i<=n;i++){
		for(s=0;s<=maxx;s++){
			for(ss=0;ss<=maxx;ss++){
				if(judge2(s,ss)){//判断第i-1行与第i行情况是否兼容 
					dp[i][ss]+=dp[i-1][s];
				}
			}
		}
	}
	a[n][m]=a[m][n]=dp[n][maxx];
	cout<<a[n][m]<<endl;
}
int main(){
	int i,j;
	memset(a,-1,sizeof(a));
	while(scanf("%d%d",&n,&m)!=EOF&&n&&m){
		if(a[n][m]!=-1){//不为-1则代表以及得出答案 
			cout<<a[n][m]<<endl;
			continue;
		}
		if((n*m)%2==1){//如果长和宽都为奇数,则方案数为0 
			a[n][m]=a[m][n]=0;
			cout<<a[n][m]<<endl;
			continue;
		}
		solve();
	}
	return 0;
}