比赛 20150421 评测结果 C
题目名称 走道铺砖问题 最终得分 0
用户昵称 wolf. 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-04-21 11:32:51
显示代码纯文本
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
long long f[13][2050];
_Bool adj[2050][2050];    //所有可能的转移
int W,H;
void dfs(int from,int step,int to)
{
   if(step == W)
   {
       adj[from][to] = 1;
       return;
   }
   if(((1 << step) & from) != 0)    //已经放过,考察下一个
       dfs(from,step + 1,to);
   else
   {
       if((step <= W - 2) && ((1 << (step + 1)) & from) == 0)    //两块都是空的,可以横放
               dfs(from,step + 2,to);
       dfs(from,step + 1,to | (1 << step));   //竖着放
   }
}
int main()
{
   freopen("floor.in","r",stdin);
   freopen("floor.out","w",stdout);
   scanf("%d%d",&W,&H);
   if((W * H) % 2 == 1)    //无解情况
   {
       printf("0\n");
       fclose(stdout);
       exit(0);
   }
   int max = 1 << W;
   int i,j,k;
   for(i = 0;i < max;i ++)    //DFS构建矩阵
       dfs(i,0,0);
   f[0][0] = 1;
   for(i = 0;i < H;i ++)
       for(j = 0;j < max;j ++)
           for(k = 0;k < max;k ++)
               if(adj[j][k])    f[i + 1][k] += f[i][j];
   printf("%I64d\n",f[H][0]);
   fclose(stdout);
   return 0;
}