$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. 先考虑横着的再考虑竖着的，横着的合法方案数就是总方案数
2. f[i][j] 表示前 i-1 列已排好，从第 i-1 列到第 i 列的竖着的状态是 j 的方案数
3. f[i][j] 和 f[i-1][k]，状态 j 和状态 k 两者不能有交集，且必须合法（即第 i-1 列剩下连续格子是偶数）
4. 先预处理所有的合法状态
5. 再预处理对于状态 j 有哪些状态 k 可以与之匹配
6. 状态转移方程：f[i][j] += f[i-1][k]

完整代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int n, m;
LL f[N][M];
bool st[M];
vector<int> state[M];

int main() {
    while (cin >> n >> m, n || m) {
        //1. 预处理出哪些状态是合法状态
        for (int i = 0; i < 1 << n; i++) {
            int cnt = 0;
            bool is_valid = true;
            for (int j = 0; j < n; j++)
                if (i >> j & 1) {
                    if (cnt & 1) {
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                } else cnt++;

            if (cnt & 1) is_valid = false;
            st[i] = is_valid;
        }

        //2. 预处理出对于状态 j 可以有哪些状态 k 可以与之匹配
        for (int j = 0; j < 1 << n; j++) {
            state[j].clear();
            for (int k = 0; k < 1 << n; k++)
                if ((j & k) == 0 && st[j | k])
                    state[j].push_back(k);
        }

        //3. dp 部分
        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;
    }

    return 0;
}