记录编号	581611	评测结果	AAAAAAAAAA
题目名称	[POJ2411] Mondriaan's Dream	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.187 s
提交时间	2023-08-08 19:21:49	内存使用	5.95 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 13,M = (1<<11)+10;
int n,m,s[M];
long long f[N][M];
bool check(int x){//判断该状态是否符合横放
//即两个相邻的1中间必须有偶数个0 
	int cnt = 0;
	for(int j = 1;j <= m;j++){
		if(x & 1){
			if(cnt % 2)return 0;//奇数个不符 
			cnt = 0;
		}
		else cnt++;
		x >>= 1;
	}
	if(cnt % 2)return 0;
	return 1;
}
int main(){
	freopen("examfive.in","r",stdin);
	freopen("examfive.out","w",stdout);
	while(scanf("%d%d",&n,&m) && n && m){
		memset(f,0,sizeof(f));
		memset(s,0,sizeof(s));//多组数据记得重置!!! 
        for(int i = 0;i < (1<<m);i++)
    	    if(check(i))s[i] = 1,f[1][i] = 1;//初始化s数组,顺便初始化f[1] 
		for(int i = 2;i <= n;i++){
			for(int j = 0;j < (1<<m);j++){//当前行的状态为j 
				for(int p = 0;p < (1<<m);p++){//上一行的状态为p 
					if((p&j) || !s[p|j])continue;//上下不能重,且符合横着放的标准 
					f[i][j] += f[i-1][p];
				}
			}
		}
		printf("%lld\n",f[n][0]);//最后一行不能有竖着的 
	}
	
	return 0;
	
}