常规做法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
/*
思想
    先放横着的，再放竖着的
    则总方案数等于只放横着的小方块的合法方案数
    如何判断当前方案是否合法：
        即判断剩余位置是否能填充满竖着的小方块
        因此可以按列来看：每一列内部所有连续的空着的小方块，需要是偶数个
状态表示
    集合表示：
        f[i,j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的所有方案
        伸出的状态是j（j用二进制表示状态，1表示伸出，0表示没有伸出）
    属性：方案数
状态计算
    f[i][j] += f[i-1][k]
        k从0到2^n
        当且仅当可从k状态转移到j状态
*/

const int N = 12, M = 1<<N;
int n, m;
long long f[N][M];
// st表示状态是否合法
bool st[M];

int main()
{
    while(cin >> n >> m, n||m)
    {
        // 遍历n行每行是否往外伸的所有情况代表的i
        // 比如n==4时，1001合法，1100合法，1011不合法
        for (int i = 0; i < 1<<n; ++i)
        {
            // cnt表示连续空着的方块的长度
            int cnt = 0;
            st[i] = true;
            for(int j=0; j<n; j++)
            {
                // 如果当前这一位即第j位是1
                if(i>>j & 1)
                {
                    // 则判断前面是否有奇数个0
                    if(cnt & 1)
                        st[i] = false;
                    cnt = 0;
                }
                else cnt++;
            }
            // 判断最后剩余的0
            if(cnt & 1)
                st[i] = false;
        }
        // 每组案例重置充值f
        memset(f, 0, sizeof(f));
        // 已经将前-1列摆好，且从第-1列伸出到第0列，
        // 伸出的状态是0的方案只有一种：什么都不放
        f[0][0] = 1;

        // 遍历列
        for(int i=1; i<=m; i++)
            // 遍历当前列的状态
            for(int j=0; j < 1<<n; j++)
                // 遍历上一列的状态
                for(int k=0; k < 1<<n; k++)
                    // 可以从上一列的状态转移到当前j状态
                    // 满足：前后不在同一行；
                    // 注意，&优先级低于==
                    // k表示伸到当前列的状态，j表示伸出当前列的状态
                    // 横着的长方形长度为2，所以要计算二者的并集
                    // 要从k到j合法，则都伸后当前列连续0个数要时偶数，即st==true
                    if((j&k)==0 && st[j|k])
                        f[i][j] += f[i-1][k];
        // 棋盘下标从0开始，前m列已经摆好，则第m列的状态0
        // （即什么都没伸到第m列）的方案数即为所求
        cout << f[m][0] << endl;
    }
}

优化做法

先把所有合法转移存储起来

 #include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 12, M = 1<<N;
int n, m;
long long f[N][M];
// state[j]表示所有能转移到j的合法状态有哪些
vector<int> state[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)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt++;
            if(cnt & 1)
                st[i] = false;
        }

        for(int i=0; i < 1<<n; i++)
        {
            state[i].clear();
            for(int j=0; j < 1<<n; j++)
                if((i&j) == 0 && st[i|j])
                    state[i].push_back(j);
        }

        memset(f, 0, sizeof(f));
        f[0][0] = 1;

        for(int i=1; i<=m; i++)
            for(int j=0; j < 1<<n; j++)
                for(auto k : state[j])
                    f[i][j] += f[i-1][k];
        cout << f[m][0] << endl;
    }
}