这题的关键是将方案数转换成求横放方块的方案数

状态表示：$f[i][j]$表示已经摆完前i列，从第$i-1$列伸出来的方块的状态是$j$的方案数，$j$是一个二进制表示数其中$i$是从0开始的，0是第1列,$m-1$是最后一行

限制条件：
1.不存有方块伸到第$i-1$列，同时有方块伸到第$i$列的状态；即要满足：第$i-1$行的状态 & 第$i$行的状态 == 0
2.前后两列的方块交错后，不存在连续奇数的空格；（需要预处理）

状态转移方程：$f[i][j] += f[i-1][k]$;

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 12 , M = 1 << N;

long long f[N][M];//f[i][j]表示的是从第i-1列伸出方块的状态是j的方案数
bool st[M];

int main()
{

    int n , m;
    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)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                }
                else cnt++;
            }
            if(cnt & 1) st[i] = false;
        }

        memset(f , 0 , sizeof f);

        //从0开始，0是第一列
        f[0][0] = 1;//伸到0（第1列）的方案数只有1种，即没有方块伸到0（第1列），该题的递归基
        for(int i = 1 ; i <= m ; i++)
            for(int j = 0 ; j < 1 << n ; j++)//枚举i（第i+1列）的状态
                for(int k = 0 ; k < 1 << n ; k++)//枚举i-1（第i列）的状态
                    if((j & k) == 0 && st[j | k])//不存有方块伸到该列，同时有方块伸到后一列列；前后两列交错后不存在连续奇数空格的情况
                        f[i][j] += f[i - 1][k];

        cout << f[m][0] << endl;//输出的是已经摆完前m列，并且没有方块伸到第m+1列的方案数
    }

    return 0;
}