原题链接

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

Sample Input

1 2

1 3

1 4

2 2

2 3

2 4

2 11

4 11

0 0

Sample Output

1

0

1

2

3

5

144

51205

/*
在位置(i, j) 如果我们选择横着贴砖，那么将(i, j), (i, j+1)都
填写成1， 如果竖着贴砖，我们将(i,j)填写成0，将(i+1, j)填写成1. 
1和0 表示的意义：
1表示当前这块砖对于下一行没有影响
如：如果是横着放砖,下一行的这个位置不管是竖着放或者横着放都可以
0则表示当前位置这块砖会对下一行同样位置造成影响
如：若竖着放 当前这一行则是这块砖的上半部分,下一行相同位置必然是这块砖的下半部分(也就是1)  
-------------
所以,如果按照这样来放砖的话,最后一行必然全是1
这样的话,每一行的状态都是一个二进制表示的数.
并且最后一行所表示的数是固定的.(因为全是1);
恒为(2^m-1),这样的好处表示方便我们输出最后的答案. 
DP(i,j)表示如下含义:当第i行,达到状态j的时候,所能采取的方案数目.
所以明显我们的最后目的是求DP(N, 2^M-1); 
每一行的状态可以直接暴力枚举. 
*/
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define rg register
int n,m;
long long dp[15][1<<15];
inline bool inti(int state)//预处理 
{
    for(rg int i=0;i<m;)
    {
        if((state&(1<<i))!=0)//第i列为1 为横放 
        {
            if(i==m-1)//已经到了m-1列 
            {
                return false; 
            }
            if((state&(1<<(i+1)))!=0)//第i列 和第i+1列 都为1 
            {
                i+=2;//考虑i+2列; 
            }
            else//第i列为1 第i+1列为0的情况是不合法的 
            {
                return false;
            }
        }
        else//第i列为0 ,考虑i+1列 
        {
            i++;
        }
    }
    return true;
}
inline bool check(int now,int pre)
{
    for(rg int i=0;i<m;)
    {
        if((now&(1<<i))!=0)//第now行 第i列为1 
        {
            if((pre&(1<<i))!=0)//第pre行 第i列也为1 所以第i 行一定是横着放的 
            {
                if(i==m-1||(pre&1<<(i+1))==0||(now&1<<(i+1))==0)//第now行和第now-1行的第i+1都必须是1,否则是非法的
                {
                    return false;
                }
                else//否则考虑i+2列 
                {
                    i+=2;
                }
            } 
            else//第pre行第i列为0 是合法的,说明第now行第i列是竖着放的,考虑下一列。 
            {
                i++; 
            }
        }
        else//第now行 第i列为0那么第pre行的第i列应该是已经填充了的
        {
            if((pre&(1<<i))!=0)
            {
                i++;
            }    
            else
            {
                return false;
            }    
        } 
    }
    return true;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)
        {
            return 0;
        }
        if((n&1!=0)&&(m&1!=0)) //n和m均为奇数的话，矩形面积就是奇数，可知是不可能完全覆盖的
        {
            printf("0\n");
            continue;
        }
        if(n<m) //交换n和m使n较大m较小，这样能减少状态数
        {
            swap(n, m);
        }
        int tot=(1<<m)-1;
        memset(dp,0,sizeof(dp));
        for(rg int i=0;i<=tot;++i)
        {
            if(inti(i)==1)
            {
                dp[1][i]=1;
            }
        }    
        for(rg int i=2;i<=n;++i) //按行dp
        {
            for(rg int j=0;j<=tot;++j) //第i行的状态
            {
                for(rg int k=0;k<=tot;++k) //第i-1行的状态
                {
                    if(check(j, k)==1)
                    {
                        dp[i][j]+=dp[i-1][k];
                    }
                }
            }
        }
        printf("%lld\n",dp[n][tot]);
    }
}