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.

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.

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 using namespace std;

 __int64 d[][<<], f[<<];//用———int64,因为有可能数很大

 int h, w, full;

 bool ok(int x) //判断一行里是否出现连续奇数个1，第一行的话不允许

 {

     int sum = ;

     while(x>)

     {

         if((x&)==)

         sum++;

         else

         {

             if((sum&)==)

             return false;

             sum = ;

         }

         x = (x>>);

     }

     if((sum&)==)

             return false;

     return true;

 }

 bool check(int x1, int x2)

 {

     int xx = (<<w)-;

     if((x1|x2)==xx&&f[x1&x2])//去掉竖着00和竖着单独11的情况，一定不要忘了单独11的情况

     return true;

     return false;

 }

 int main()

 {

     int i, j, k;

     memset(f, , sizeof(f));

     full = (<<);

     for(i = ; i < full; i++)

     if(ok(i))

     f[i] = ;   //记录连续的奇数个1

     while(~scanf("%d%d", &h, &w))

     {

         if(h==&&w==)

         break;

         full = (<<w);

         memset(d, , sizeof(d));

         for(i = ; i < full; i++)

         if(f[i])

         d[][i] = ;

         for(k = ; k < h; k++)

         for(i = ; i < full; i++)

         for(j = ; j < full; j++)

         {

             if(check(i, j))

             d[k][i] += d[k-][j];

         }

         printf("%I64d\n", d[h-][full-]); //最后一行，而且满1

     }

     return ;

 }