讲解都在代码里了

C++ 代码

//思路：找出只放横向1*2的格的方案，然后把竖向的格子塞进空着的位置， 用二进制来表示格子是否被填充。
//状态表示：f[i][j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的状态是j的所有方案
//f[i][j] = f[i-1][k1] + f[i-1][k2] +...+ f[i-1][kn].  k1,k2,...,kn 是合法的情况
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 12, M = 1 << N;

long long f[N][M];
bool st[M];

int main()
{
    int n, m;
    while(cin >> n >> m, n || m)
    {
        //row:19-35  是预处理出所有成立的情况
        for(int i = 0; i < 1 << n; i++)
        {
            int cnt = 0;
            st[i] = true;//假设情况i成立
            for(int j = 0; j < n; j++)
                if(i >> j & 1)//判断i的每位是否是1, if成立的条件是i该位是1.
                {
                    //若连续的一段0的个数为奇数，就无法用竖向格子去填充，该情况不成立
                    if(cnt & 1) st[i] = false;
                    cnt = 0;//该段连续的0判断完毕，重置cnt去记录下段连续0的个数。
                }
                else    cnt++;//若 不是1就加加

            //最后一段0的情况 
            if(cnt & 1) st[i] = false;
        }

        //初始化f
        memset(f, 0, sizeof f);
        //f[0][0]表示从-1列伸出到第0列状态为0（即：第0列格子都未被填充）的方案 默认为1.
        f[0][0] = 1;
        //从第1列到第m列 遍历m列
        for(int i = 1; i <= m; i++)
            for(int j = 0; j < 1 << n; j++)
                for(int k = 0; k < 1 << n; k++)
                    if((j & k) == 0 && st[j | k])//j&k==0 表示状态j与状态k没有重合，j|k表示两状态之间0的个数是否合法
                        f[i][j] += f[i-1][k];

        cout << f[m][0] << '\n';
    }


    return 0;
}