题意理解

在 $n \times m$ 的网格中，有障碍格 # 和空格 .。 要求用恰好三个互不相交的 $L$ 形块（每个 $L$ 形占 $2 \times 2$ 的子方格中的 $3$ 个格子，且不能是直线形）铺满所有空格，且 $L$ 形之间、$L$ 形与障碍之间不能重叠。 求方案数。

关键思路

1. $L$ 形的表示

每个 $L$ 形可以看作一个 $2 \times 2$ 方块去掉一个格子。 在插头 DP 中，我们用括号表示法（轮廓线 DP）来记录连通性，并用状态记录当前已放置的 $L$ 形数量。

2. 插头 DP 状态设计

设 $f(s, nb)$ 表示当前处理到某个格子，轮廓线状态为 $s$，已经放置了 $nb$ 个 $L$ 形时的方案数。

$s$ 用四进制表示每列的插头类型：

$0$：无插头

$1$：$L$ 形的左括号（开始）

$2$：$L$ 形的右括号（结束）

$nb \le 3$ 表示已放置的 $L$ 形数量。

3. 状态转移

设当前格子 $(i,j)$，轮廓线上对应位置 $x$（当前列）和 $y$（下一列）的插头状态。

情况 1：障碍格

如果 $a[i][j] = 0$（障碍）：

必须 $x = 0, y = 0$ 才能转移，保持状态不变。

情况 2：空格且无插头 ($x=0, y=0$)

不放 $L$ 形：保持状态。

如果 $nb < 3$，可以在此开始一个新的 $L$ 形：将 $x$ 设为 $1$。

情况 3：空格且 $x=0, y=1$

$y=1$ 表示上一行此列有 $L$ 形开始，现在可以：

向右延伸：将 $y$ 改为 $2$（结束）。

向下延伸：将 $x$ 设为 $1$，$y$ 设为 $0$。

情况 4：空格且 $x \neq 0, y=0$

如果 $x=1$：可以向右结束：将 $x$ 设为 $0$，$y$ 设为 $1$。

如果 $x=2$：可以向下结束：将 $x$ 设为 $0$；或者向右继续：将 $x$ 设为 $0$，$y$ 设为 $2$。

4. 换行处理

每行结束时，轮廓线状态左移 $2$ 位（因为列数增加一个虚拟列），并检查最后一列不能有未匹配的左括号（$gw(s, m+1) = 0$）。

5. 最终条件

当处理完最后一行 $(i=n)$，且轮廓线状态 $s=0$（所有插头匹配完毕），且 $nb=3$（恰好三个 $L$ 形）时，累加方案数。

算法复杂度

状态数：$O(4^m \times 4)$（$m \le 30$ 但有效状态很少） 使用滚动数组 + HashMap 存储状态，实际可运行。

代码关键函数

gw(s, i)：获取状态 $s$ 中第 $i$ 列的插头值（$2$ 位四进制）。

sw(s, i, w)：将状态 $s$ 中第 $i$ 列设为 $w$。

使用 map<pair<ll, int>, ll> 作 DP 表，第一维是 $(s, nb)$，第二维是方案数。

总结

本题是带数量限制的插头 DP，通过四进制状态表示 $L$ 形的连通分量，并限制 $L$ 形数量不超过 $3$，最终要求铺满且数量恰好为 $3$。 这是一种经典的骨牌覆盖变种，适合用轮廓线 DP 解决。