个人建议直接看算法进阶指南那个视频。也就是第一个视频。

题意分析：
由题意可知，通过二进制来表示每一列长方形的状态，列如10000 表示就第一行的长方形伸出来
状态表示：f[i][j]为在前i-1列全部摆完的情况下，i-1行伸出来的状态为j，j就是类似于上面具体的二进制数。

由此计算需要满足两个条件：
先进行横着放置长方形
1 .从i-1列伸出来的长方形，不应与第i列伸出来的长方形产生冲突，如果产生冲突，就是产生长方形形成重叠。 谨记：这时的状态分别为：i-1列伸出的状态为起点从第i-2列伸出来的，第i列伸出来的状态为从第i-1列伸出来的 因此需要满足j&k==0 （j和k分别为i-1行和第i行的状态，都为二进制数）
之后进行竖着放置长方形
2.从列的方向上，看j或者k的状态，可得，不存在连续奇数的空格，即为连续的0.但是到每一列的最后一行中，可能会出现奇数0的个数，这时需要去进行处理。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N =12,M=1<<N;
int n,m;
long long f[N][M];
bool st[M];

int main()
{
   while(cin>>n>>m,n||m)
      {
          for(int i=0;i<1<<n;i++)
          {
              int cnt=0;
              st[i]=true;
              for(int j=0;j<n;j++)  //遍历每一行
                  if(i>>j&1)    //遍历n行
                  {
                      if(cnt&1)  st[i]=false;   //不符合条件，排除这种方案
                      cnt=0;  //表示到现在为止，一共有多少个连续的0
                  }
                  else   
                  cnt++;
               if(cnt&1)  st[i]=false;//就是最后一列中的最后一个状态不是以0结尾
          }

          memset(f,0,sizeof f);
          f[0][0]=1;
          for(int i=1;i<=m;i++)   //每一列
             for(int j=0;j<1<<n;j++)   //第i行的状态
                for(int k=0;k<1<<n;k++)  //第i-1的状态
                  if((j&k)==0&&st[j|k])  //i-1列的状态和第i行的状态不能重复，即&为0。
                  f[i][j]+=f[i-1][k];
                  cout<<f[m][0]<<endl;  //表示前m-1列已经摆放完毕，并且当前的状态都为0，即没有长方形伸出来。//如果伸出来，则已经出界。
    }
    return 0;
}