$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

观察到 $n,m \leq 11$，考虑状压 DP。
发现如果我们确定了所有竖着放的砖块，就可以判定横向放砖块是否合法，而且还可以求出上下行之间哪些匹配方案合法，从而实现状态转移。
观察影响因素，设 $dp_{i,S}$ 表示前 $i$ 行，最后一行状态为 $S$ 的方案数，$S$ 记录的是上一行延伸下来的位置。

那么能由 $S_1$ 转移到 $S_2$ 仅当 $S_1 \& S_2 = 0$（没有交集不会重叠）且 $S_2$ 是满足条件的。
这里称一个状态是“满足条件的”，当且仅当它所有连续 $0$ 段长度都是偶数，这样才可以放横着的砖块。

状态定义的属性是方案数，显然直接累加即可。
注意 long long。

#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = (1 << 11) + 15;
bool st[M]; //i 是否满足条件
int n, m;
long long dp[N][M];

void init() {
    memset(st, 0, sizeof st);
    for (int i = 0; i < (1 << m); i++) {
        int cnt = 0; st[i] = true;
        for (int j = 0; j < m; j++) {
            if ((i >> j) & 1) {
                if (cnt & 1) {
                    st[i] = false;
                    cnt = 0;
                    break;
                }
                cnt = 0;
            } else cnt++;
        }
        if (cnt & 1) st[i] = false;
    }
    // for (int i = 0; i < (1 << m); i++)
    //     if (st[i]) cout << i << ' '; puts("");
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        if (n == 0 && m == 0) break;
        init();
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < (1 << m); j++)
                for (int k = 0; k < (1 << m); k++)
                    if ((j & k) == 0 && st[j | k]) dp[i][j] += dp[i - 1][k];

        printf("%lld\n", dp[n][0]);
    }
    return 0;
}