acm-pku2411.txt

北京大学 acm网站2411题的解题源码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

//const
const int Max=2050;
//var
int m,n;
long long f[12][Max];

//...............................................................................
//...............................................................................

int dfs(int i,int s1,int s2,int p){
	if(p==n){
		f[i+1][s2]+=f[i][s1];
	}else if(s2&(1<<p)){
		dfs(i,s1,s2&~(1<<p),p+1);
	}else{
		dfs(i,s1,s2|(1<<p),p+1);
		if(p<n-1 && (s2&(1<<(p+1)))==0)
			dfs(i,s1,s2,p+2);
	}
	return 0;
}//dfs

int main(){
		
	//********************
	int i,j;
	//********************

	while(scanf("%d%d",&m,&n),m+n!=0){
		memset(f,0,sizeof(f));
		f[0][0]=1;
		if(m%2==1 && n%2==1){
			printf("0\n");
		}else{
			for(i=0;i<m;++i)
				for(j=0;j<(1<<n);++j)
					if(f[i][j])
						dfs(i,j,j,0);
			printf("%I64d\n",f[m][0]);
		}
	}
	return 0;
}//main