- Mondriaan's Dream
- 记忆化搜索
- @ 2025-6-28 11:12:04
#include<bits/stdc++.h>
using namespace std;
long long f[12][1<<11];
long long h,w;
bool check(long long pp){
	long long cnt=0;
	for(int i=0;i<w;i++){
		if(pp&(1<<i)){
			if(cnt&1) return false;
			cnt=0;
		}else cnt++;
	}
	return (cnt&1)==0;
}
long long dp(long long d,long long pp){
	if(d==0)return pp==0;
	if(f[d][pp]!=-1)return f[d][pp];
	long long ans=0;
	for(int i=0;i<(1<<w);i++){
		if((i&pp)==0&&check(i|pp)){
			ans+=dp(d-1,i);
		}
	}
	return f[d][pp]=ans;
}
long long jg(){
	memset(f,-1,sizeof f);
	return dp(h,0);
}
int main(){
	while(cin>>h>>w){
		if(h==0&&w==0)break;
		cout<<jg()<<endl;
	}
}
0 comments
  
  No comments so far...
            Information
- ID
- 405
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 26
- Accepted
- 11
- Uploaded By
 
      