记录编号	159478	评测结果	AAAAAAAAAA
题目名称	走道铺砖问题	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.173 s
提交时间	2015-04-21 17:17:30	内存使用	13.76 MiB

#include<cmath>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 41
#define INF ((1<<M)-1)
#define LL long long
#define BASE 10000
using namespace std;
class HPint{
public:
	int n;
	int s[20];
	HPint(){n=1;memset(s,0,sizeof(s));}
	void operator = (int x){
		memset(s,0,sizeof(s));
		n=1;
		s[0]=x;
	}
	void operator += (const HPint &b){
		n=max(n,b.n)+1;
		for(int i=0;i<n;i++){
			s[i]+=b.s[i];
			s[i+1]+=s[i]/BASE;
			s[i]%=BASE;
		}
		while(n>1&&s[n-1]==0) n--;
	}
	void print(){
		printf("%d",s[n-1]);
		for(int i=n-2;i>=0;i--) printf("%04d",s[i]);
	}
};
int N,M;
HPint F[MAXN][1<<12];
void DFS(int x,HPint s,int p,int k)
{
	F[p+1][x]+=s;
	for(int i=k;i<M;i++) 
		if((!((x>>(M-i))&1))&&(!((x>>(M-i-1))&1))) 
			DFS(x+(1<<(M-i))+(1<<(M-i-1)),s,p,i+2);
}
int main()
{
	freopen("floor.in","r",stdin);
    freopen("floor.out","w",stdout);
	cin>>N>>M;
	if(N<M) swap(N,M);
	for(int i=0;i<=N;i++) for(int j=0;j<=INF;j++) F[i][j]=0;
	F[0][INF]=1;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=INF;j++)
		{
			int x=(~j)&INF;
			DFS(x,F[i][j],i,1);
		}
	}
	F[N][INF].print();
	return 0;
}