代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e1 + 2, M = 1 << N;

typedef long long ll;

int n, m;
ll dp[N][M];  // dp[i][j] 表示已经将前 i-1 列摆好， 且从第 i-1列伸出到第 i 列的状态是 j 的所有方案
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;
                    }
                    cnt = 0;
                }
                else {
                    cnt++;
                }
            }
            if (cnt & 1) {
                st[i] = false;
            }
        }
        memset(dp, 0, sizeof dp);
        dp[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++) {
                    if ((j & k) == 0 && st[j | k]) {
                        // j & k == 0 表示 i 列和 i - 1列同一行不同时捅出来
                        // st[j | k] == 1 表示 在 i 列状态 j， i - 1 列状态 k 的情况下是合法的.
                        dp[i][j] += dp[i - 1][k];
                    }
                }
            }
        }
        cout << dp[m][0] << endl;
    }
    return 0;
}