比赛 20150421 评测结果 AAAAWWWWWW
题目名称 走道铺砖问题 最终得分 40
用户昵称 Dijkstra 运行时间 0.077 s
代码语言 C++ 内存使用 1.59 MiB
提交时间 2015-04-21 09:09:17
显示代码纯文本
#include<fstream>
#include<cmath>
#include<cstring>
#define MAXN 41
#define INF ((1<<M)-1)
#define LL long long
using namespace std;
ifstream fin("floor.in");
ofstream fout("floor.out");
int N,M;
LL F[MAXN][1<<12];
void DFS(int x,LL 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()
{
	fin>>N>>M;
	if(N<M) swap(N,M);
	memset(F,0,sizeof(F));
	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);
		}
	}
	fout<<F[N][INF]<<endl;
	return 0;
}