1 #include <iostream>
2 using namespace std;
3 typedef __int64 LL;
4 #define MaxSize 12
5 LL num[MaxSize][MaxSize];
6 LL dp[MaxSize][2049];
7 int h,w,MaxN;
8
9 bool test(int val){
10 int i,sum;
11 for(i=0;i<w;i++){
12 sum=0;
13 while (val & (1<<i))
14 sum++,i++;
15 if(sum & 1) return false;
16 }
17 return true;
18 }
19 LL getAw(int step,int status){
20 if(step==1){//临界状态
21 if(test(status)) return 1;
22 return 0;
23 }
24 if(dp[step][status]!=-1)
25 return dp[step][status];
26 int i,temp,last=~status;
27 LL sum=0;
28 last &= MaxN;
29 for(i=0;i<=MaxN;i++){
30 if( (i&last) != last)
31 continue;
32 temp=i & status;
33 if(test(temp))
34 sum+=getAw(step-1,i);
35 }
36 dp[step][status]=sum;
37 return sum;
38 }
39
40 int main(){
41 //freopen("in.txt","r",stdin);
42 memset(num,-1,sizeof(num));
43 while (scanf("%d %d",&h,&w),(h||w)){
44 if(h*w & 1){
45 puts("0");
46 continue;
47 }
48 if(h<w)
49 h^=w,w^=h,h^=w;
50 if(num[h][w]!=-1){
51 printf("%I64d\n",num[h][w]);
52 continue;
53 }
54 int i,j;
55 MaxN=(1<<w)-1;
56 for(i=1;i<=h;i++)
57 for(j=0;j<=MaxN;j++)
58 dp[i][j]=-1;
59 num[h][w]=num[w][h]=getAw(h,MaxN);
60 printf("%I64d\n",num[h][w]);
61 }
62 return 0;
63 }
posted on 2012-07-14 14:55
Leo.W 阅读(343)
评论(0) 编辑 收藏 引用