【模板】插头 dp 题解

link
给定一个 $n \times m​$ 的方格，有些格子不能铺线，其他格子必须铺，求构成一个闭合回的方案数。
$ 2 \le n,m \le 12$

一个很显然的性质，因为是回路，所有要铺的格子都是一进一出两条线。

状态

考虑 dp，$f_{i, j, s}$ 当前决策到第 $i$ 行第 $j$ 个格子，状态为 $s$ 的方案数。

$s$ 的状态为当前决策的格子和未决策的格子之间的分界线，即轮廓线上有没有线穿过。

一个被引用不知多少次的好多题解都有的图

可以看到轮廓线的长度是 $m + 1$。

这里 $s$ 我知道的有两种存法，一种是最小表示法，一种是括号序列。

最小表示法很直观，没有线就是 $0$，有线的话，一条线有两个线头，给这两个线头一个相同的标号。这样我们就得到一个状态，比如图中轮廓线状态可以表示为 12201。但这样一个状态可能会有多个表示，像图中 32203 也是它的一个表示，所以用最小表示法求出它的唯一状态。

但个人感觉括号序列更简洁易懂，所以关于最小表示法就不展开了。

---

一条线两个线头，一左一右；另外我们之前已经得到，所有格子都是一进一出，不会有两条线相交。

聪明的你是不是已经发现了，这些性质与括号序列、括号匹配多么吻合。

确实，我们可以用 0 表示没线头，1 表示左括号，即左边的线头； 2 表示右边的线头。线不相交巧妙地保证了一个轮廓线状态只会有一个表示。

解决了状态，接下来就是转移了。

转移

我们计这个格子左边的状态为 $l$，$0$ 表示不连，$1$、$2$ 分别表示是左/右线头。同理计上面是否连为 $u$，右和下分别为 $r$、$d$。

可以发现，$l$ 所对应的就是 $s$ 中的第 $j$ 位，$u$ 就是第 $j + 1$ 位，我们的转移就是把 $l$、$u$ 转化为 $d$、$r$。

我们采用向后推的方式转移，也就是我们需要考虑在 $s$ 的状态下 $i$ 行 $j$ 列这个格子可以怎么连线。

Case 1

l = 0, u = 0。

最简单的，左边上面都不连，要连两个线头的话只能是右和下都连了，即新开了一对括号。

r = 1, d = 2。

Case 2

l = 0, u != 0。

从上面可以连到右或下，并延续之前的括号状态。

r = u, d = 0 或 r = 0, d = u。

Case 3

l != 0, u = 0。

与第二个情况类似。

r = l, d = 0 或 r = 0, d = l。

---

接下来的情况 $l$，$u$ 都不为零，所以 $r$，$d$ 都是零。

Case 4

l = 2, u = 1

两个区间的合并。

Case 5

l = 1, r = 1

同样是两个区间的合并，但不一样的是为了保证状态的正确性，我们要找到 $l$ 对应的右括号改为左括号。

Case 6

l = 2, r = 2

与 5 类似，找到 $u$ 对应的左括号改为右括号。

Case 7

l = 1, r = 2

为什么这个状态要放到最后讲呢，别忘了线不能相交，所以这个左右括号一定是对应、匹配的一对，这种情况出现代表着右一条线闭合了。这种情况只能在最后一个格子发生一次，此时更行答案。

---

至此转移也完成了！乌拉————

关于实现

实现中状态使用了四进制，并且实际上是倒着的，方便利用位运算简化代码。

---

会有很多的冗余状态，哈希或map就是在这里用的。

---

在转移时我们用到了三个对 $s$ 的操作：

• 取出其中一位；
• 修改其中一位；
• 查找一个括号对应的另一个括号。

写成函数可以方便处理。

---

在每行最后是要特殊处理的！我们要改变一下轮廓线：

如图，要舍去第五位不为 $0$ 的状态，并将 $s$ 右移 $2$ 位（空出一个位置）。

---

最后一个格子应该是最后一个必须铺线的格子。

---

建议数组滚起来防止炸掉。

---

需要 long long。

CODE

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}

#define N 14
#define int long long

int n, m, a[N][N], lst;
int res;

unordered_map<int, int> f, g;

inline int get(int st, int x) {
    return ((st >> (x - 1 << 1)) & 3);
}
inline void chg(int &st, int x, int v) {
    st ^= (st >> (x - 1 << 1) & 3) << (x - 1 << 1);
    st ^= v << (x - 1 << 1);
}
inline int fid(int st, int x, int s = 0) {
    if (get(st, x) == 1) {
        for (x ++; s != 1; x ++) {
            int t = st >> (x - 1 << 1) & 3;
            if (t == 1) s --;
            if (t == 2) s ++;
        }
        return x - 1;
    } else {
        for (x --; s != 1; x --) {
            int t = st >> (x - 1 << 1) & 3;
            if (t == 1) s ++;
            if (t == 2) s --;
        }
        return x + 1;
    }
}

signed main() {
    for (int T = read(); T --;) {
        memset(a, 0, sizeof a), f.clear(), g.clear(), res = 0;
        n = read(), m = read();
        int op = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                a[i][j] = read();
                op |= a[i][j];
            }
        }
        if (!op) {
            puts("1");
            continue;
        }

        lst = n * m;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                if (a[i][j]) lst = i * (m - 1) + j;
            }
        }
        f[0] = 1;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                for (auto k : f) {
                    int st = k.first, val = k.second;
                    int l = get(st, j), u = get(st, j + 1);
                    int r = a[i][j + 1], d = a[i + 1][j];
    
                    if (a[i][j] == 0) {
                        if (l == 0 && u == 0) g[st] += val;
                        continue;
                    }
                    if (l == 0 && u == 0) {
                        chg(st, j, 1), chg(st, j + 1, 2), g[st] += val;
                    }
                    if (l == 0 && u != 0) {
                        if (r) g[st] += val;
                        if (d) chg(st, j, u), chg(st, j + 1, 0), g[st] += val;
                    }
                    if (l != 0 && u == 0) {
                        if (d) g[st] += val;
                        if (r) chg(st, j + 1, l), chg(st, j, 0), g[st] += val;
                    }
                    if (l == 2 && u == 1) {
                        chg(st, j, 0), chg(st, j + 1, 0), g[st] += val;
                    }
                    if (l == 1 && u == 1) {
                        int t = fid(st, j + 1);
                        chg(st, j, 0), chg(st, j + 1, 0), chg(st, t, 1), g[st] += val;
                    }
                    if (l == 2 && u == 2) {
                        int t = fid(st, j);
                        chg(st, j, 0), chg(st, j + 1, 0), chg(st, t, 2), g[st] += val;
                    }
                    if (l == 1 && u == 2) {
                        chg(st, j, 0), chg(st, j + 1, 0);
                        if (i * (m - 1) + j == lst && st == 0) res += val;
                        else if (i * (m - 1) + j != lst) g[st] += val;
                        continue;
                    }
                }
                f.swap(g), g.clear();
            }
            for (auto k : f) {
                if (k.first < (1 << (m << 1))) g[k.first << 2] = k.second;
            }
            f.swap(g), g.clear();
        }
    
        printf("%lld\n", res);
    }
    return 0;
}

等我一会多添点图