比赛 |
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;
}