形式化题目

给定 $N \times M$ 的棋盘（$1 \le N, M \le 11$），用若干 $1 \times 2$ 的骨牌不重叠地铺满它，求铺满的方案数。骨牌可以横放也可以竖放，棋盘必须被完全覆盖，不能有重叠也不能留空格。多组询问，以 0 0 结束。

思路

朴素做法及其困境

最直接的想法是给每个格子依次决定放什么牌，但骨牌是横跨两个格子的：放一张横牌会影响右邻格，放一张竖牌会影响下一行。如果只记录"扫到哪个格子"，无法知道哪些格子已经被之前的牌占住了，决策无从做起。所以状态里必须携带"当前格之前的格子被谁占了"的完整信息。

逐行划分 + 列压缩状态

把棋盘按行划分阶段。逐行填放，先注意一个关键性质：横牌一旦越过行边界就不存在——横牌只占同一行的相邻两格。因此行与行之间的"相互影响"只有一种来源：竖牌。一张竖牌占第 $j$ 行和第 $j+1$ 行的同一列。

于是定义：

其中 $s$ 是一个 $N$ 位二进制数，第 $pos$ 位为 1 表示第 $j+1$ 行的第 $pos$ 列已被上一行伸下来的竖牌占住。前 $j$ 行已完全填满，意味着这些伸出列就是唯一悬而未决的信息。

初始 $f_{0,0}=1$；转移时对第 $j+1$ 行做一次行内逐格 dfs，把该行剩余空格用横牌/竖牌填满，竖牌用 cur 记录向下伸出的列集合，填完后累加到 $f_{j+1,cur}$。答案为 $f_{M,0}$（所有行填完且没有向下伸出）。

行内逐格 dfs 的三种情况

设进入本行时被占列集合为 s，dfs(pos, cur) 表示正在决定第 pos 列（cur 为本行向下伸出的列集合）：

注意两点：横牌合法的前提是右邻格没有被上一行的竖牌占住；本行内每张竖牌都登记到 cur，传给下一行处理，本行自身不会出现"填一半"的状态。

为什么这样是对的

按行从上往下扫，决策只依赖"上一行传下来的伸出列集合"，不依赖更早的行（更早的行已全部填满，无法再伸出）。每个合法铺法按行的顺序、每行内按列的顺序被唯一地展开成一条决策链；反之每条以 s=0 结尾的决策链也唯一对应一个合法铺法，所以方案数被不重不漏地统计。

状态规模与记忆化

有效状态只有 $(j, s)$ 共 $(M+1) \times 2^N$ 个（本题 $12 \times 2048 \approx 2.5 \times 10^4$），行内 dfs 只是把"如何从 $f_{j,s}$ 走到各个 $f_{j+1,cur}$"展开成枚举，用 functools.cache 记忆化后每个 $(j,s)$ 只算一次，远小于所有格子的指数级决策树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 铺地砖：轮廓线 DP，逐行推进，状态是本行被上方横牌占住的列集合。
#include <cstdio>
#include <cstring>

typedef long long ll;

const ll MAXN = 13;
const ll MAXS = 1 << MAXN;

ll n, m;
ll memo[MAXN][MAXS];   // g[j][s] 的记忆化
char vis[MAXN][MAXS];

ll dfs_row(ll j, ll pos, ll cur, ll s);

// 处理第 j+1 行：进入时该行已被占列为 s，返回本行填完后传给下一行的伸出列集合的方案数
ll g(ll j, ll s) {
    if (j == m) return (s == 0) ? 1 : 0;
    if (vis[j][s]) return memo[j][s];
    ll res = dfs_row(j, 0, 0, s);
    vis[j][s] = 1;
    memo[j][s] = res;
    return res;
}

// 逐格填第 j+1 行，cur 为本行向下伸出的列集合
ll dfs_row(ll j, ll pos, ll cur, ll s) {
    if (pos == n) return g(j + 1, cur);
    ll b = 1LL << pos;
    if (s & b) return dfs_row(j, pos + 1, cur, s); // 该格已被上方横牌占据
    ll res = dfs_row(j, pos + 1, cur | b, s);      // 竖牌：向下一行伸出
    if (pos + 1 < n && !(s & (b << 1))) {          // 横牌：占 (pos,pos+1)，不伸出
        res += dfs_row(j, pos + 2, cur, s);
    }
    return res;
}

int main() {
    ll a, b;
    while (scanf("%lld %lld", &a, &b) == 2) {
        if (a == 0 && b == 0) break;
        n = a;
        m = b;
        memset(vis, 0, sizeof(vis)); // 记忆化缓存与 m 有关，每个用例必须清空
        printf("%lld\n", g(0, 0));
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41import sys
from functools import lru_cache

def solve(n: int, m: int) -> int:
    """N*M 棋盘用 1*2 骨牌铺满的方案数（轮廊线 DP）。"""
    # 按行转移：f[j][s] = 已填满前 j 行时，第 j+1 行被上方横牌占住的列集合 s 的方案数
    # 初始 f[0][0]=1，答案 f[m][0]（全部行填完且无伸出）。

    @lru_cache(maxsize=None)
    def g(j: int, s: int) -> int:
        # 处理第 j+1 行：进入时该行已被占列为 s，返回本行填完后传给下一行的伸出列集合
        if j == m:
            return 1 if s == 0 else 0
        # dfs(pos, cur)：逐格填第 j+1 行，cur 为本行向下伸出的列集合
        def dfs(pos: int, cur: int) -> int:
            if pos == n:
                return g(j + 1, cur)
            b = 1 << pos
            if s & b:  # 该格已被上方横牌占据，跳过
                return dfs(pos + 1, cur)
            res = dfs(pos + 1, cur | b)  # 竖牌：向下一行伸出
            if pos + 1 < n and not (s & b << 1):
                res += dfs(pos + 2, cur)  # 横牌：占 (pos,pos+1)，不伸出
            return res
        return dfs(0, 0)

    return g(0, 0)

def main() -> None:
    out = []
    for line in sys.stdin:
        parts = line.split()
        if len(parts) < 2:
            continue
        n, m = int(parts[0]), int(parts[1])
        if n == 0 and m == 0:
            break
        out.append(str(solve(n, m)))
    print('\n'.join(out))

main()

复杂度

• 状态数 $O(M \cdot 2^N)$，每个状态行内转移 $O(N)$ 量级（逐格 dfs 的每层只有常数分支），总复杂度 $O(M \cdot N \cdot 2^N)$。$N, M \le 11$ 时约 $3 \times 10^5$ 次基本操作，即使多组询问也可以先离线预处理所有 $1 \le N, M \le 11$ 的答案再回答。
• 空间 $O(M \cdot 2^N)$，本题用 lru_cache 隐式存储。

总结

• 核心是轮廓线 DP 的建模：阶段是行、附加信息是"下一行被竖牌占住的列集合"，一个 $N$ 位二进制足以概括行间全部影响。
• 行内用递归逐格决策，天然处理了"横牌需要右邻空、竖牌登记到下一行"的分支逻辑，比手写按列循环的写法更短。
• 这套"逐行扫描 + 列状态压缩"是棋盘覆盖类问题的通用骨架（插头 DP 的简化版），$N \le 11$ 的范围正是对 $2^N$ 状态数的暗示。

图示解析

逐行扫描与伸出列集合

以 $N=2, M=3$（样例答案 3）为例，展示三行扫描过程中伸出集合的变化：

flowchart LR
    A["j=0 进入<br/>s=00"] -->|"两格都可竖放/横放"| B["j=1<br/>s ∈ {01, 10, 11}"]
    B --> C["j=2<br/>s ∈ {00, 01, 10, 11}"]
    C -->|"最后一行后 s=0 才计数"| D["答案 = 3"]

中间行的情况对称展开，最终只有 $s \equiv 0$ 的路径存活，共 3 条。

一张牌如何影响轮廓线

flowchart TB
    subgraph row1["第 j 行 → 第 j+1 行"]
        direction LR
        V1["竖牌<br/>cur 该位记 1"] --- V2["下一行该格开局即被占"]
        H1["横牌<br/>要求右邻不在 s 中"] --- H2["两格同 row 内消化<br/>cur 不变"]
    end

绿色标记的伸出列就是状态 $s$：上一行哪里竖放了牌，下一行就在哪里"欠"一个格子。