管之水元素充盈

Makab · 2025-04-07 19:28:11 · 题解

题意

略去。

题解

很裸的插头 DP。

采用两位每列表示当前列的水管状态（共三种：0：无连接，1：左括号，2：右括号）。

考虑转移，对于每个合法的状态，在每个位置：

• 不能放：只能传递当前状态，不能新加水管。
• 是空的：
  • 不放水管：原状态传递。
  • 要放水管：尝试连接左右、上下、拐角，更新状态。

因为所有的水管必须使用，不能有多余开放端口，所以必须闭合匹配。

代码

有痕量注释。

constexpr int N = 1 << 22, MOD = 10007, SIZ = 5e6 + 114514;

int n, m, tot1, tot2;
int a[N], b[N], c[N], d[N], *f1 = a, *f2 = b, *s1 = c, *s2 = d;
int hs[SIZ], nxt[N];
char mp[12][12];

int get(int stt, int k) { return stt >> (k * 2) & 3; }
int masq(int stt, int k, int x) { return stt + x * (1 << (k * 2)); }

void trans(int stt, int dlt, int &tot) {
    int tha = stt % SIZ;
    for (int i = hs[tha]; ~i; i = nxt[i]) if (s2[i] == stt)
        return (f2[i] += dlt) %= MOD, void();
    s2[tot] = stt;
    f2[tot] = dlt;
    nxt[tot] = hs[tha];
    hs[tha] = tot++;
}

int main() {
    read(n, m);
    dep(i, 0, n) scanf("%s", mp[i]);

    // 初始状态，在首行首格存在左括号
    s1[0] = masq(0, 1, 1);
    f1[0] = 1;
    tot1 = 1;
    memset(hs, -1, sizeof(hs));

    // 枚举每个格子，按行从左到右处理
    dep(i, 0, n) {
        dep(j, 0, m) {
            tot2 = 0;
            dep(k, 0, tot1) {
                int stt = s1[k], dlt = f1[k],
                    // t1 左，t2 上
                    t1 = get(stt, j), t2 = get(stt, j + 1);

                // 移除当前格周边状态，准备重设
                stt = masq(masq(stt, j, -t1), j + 1, -t2);

                if (mp[i][j] == '#') {
                    // 当前格被禁，只能从不连转移
                    if (!t1 && !t2) trans(stt, dlt, tot2);
                    continue;
                }

                if (!t1 && !t2) { // 当前格子左右都无连接
                    trans(stt, dlt, tot2);  // 不放
                    trans(masq(masq(stt, j, 1), j + 1, 2), dlt, tot2);   // 搞一对新水管左右形成一对括号
                } else if (t1 && !t2) { // 只有左边有连接
                    trans(masq(stt, j, t1), dlt, tot2);
                    trans(masq(stt, j + 1, t1), dlt, tot2);
                } else if (!t1 && t2) { // 只有上方有连接
                    trans(masq(stt, j, t2), dlt, tot2);
                    trans(masq(stt, j + 1, t2), dlt, tot2);
                } else if (t1 == 1 && t2 == 1) {
                    int p = j + 2;
                    for (int cnt = 1; cnt; ++p) {   // 找到一个左括号
                        if (get(stt, p) == 1) ++cnt;
                        if (get(stt, p) == 2) --cnt;
                    }
                    trans(masq(stt, p - 1, -1), dlt, tot2);
                } else if (t1 == 2 && t2 == 2) {
                    int p = j - 1;
                    for (int cnt = -1; cnt; --p) {  // 找到一个右括号
                        if (get(stt, p) == 1) ++cnt;
                        if (get(stt, p) == 2) --cnt;
                    }
                    trans(masq(stt, p + 1, 1), dlt, tot2);
                } else if (t1 == 2 && t2 == 1)  // 合并
                    trans(stt, dlt, tot2);
            }
            dep(k, 0, tot2) hs[s2[k] % SIZ] = -1;
            swap(tot1, tot2); swap(s1, s2); swap(f1, f2);
        }
        dep(j, 0, tot1)
            if (get(s1[j], m)) f1[j] = 0;
            else s1[j] <<= 2;   // 左移两个比特扩展状态位
    }

    // 终止状态，只有最后一行最后一格存在一个左括号
    dep(i, 0, tot1) if (f1[i] && s1[i] == masq(0, m, 1))
        return printf("%d\n", f1[i]), 0;
    puts("0");

    return 0;
}