luogu5056 【模板】插头dp

题目描述

给出n*m的方格,有些格子不能铺线,其它格子必须铺,形成一个闭合回路。问有多少种铺法?

输入格式

第1行,n,m(2<=n,m<=12)

从第2行到第n+1行,每行一段字符串(m个字符),"*"表不能铺线,"."表必须铺

输出格式

输出一个整数,表示总方案数

样例输入

4 4
**..
....
....
....

样例输出

2

分析

插头dp教程:《基于连通性状态压缩的动态规划问题》

这里只放个模板。

代码

状态的表示采用括号序列。不过感觉最小表示法更泛用。

采用暴力移位解决哈希冲突,哈希表可以适当开大一点以降低常数。

#include <bits/stdc++.h>
typedef long long ll;

const int N = 15;
const int S = 20000;
const int P = 100007;

int n, m;
bool a[N][N];
int ex, ey;
int cur, tot[2];
int st[2][S];
ll f[2][S];
int hsh[P];
ll ans;

void init() {
    scanf("%d%d", &n, &m);
    static char r[N];
    for (int i = 0; i < n; i++) {
        scanf("%s", r);
        for (int j = 0; j < m; j++) {
            a[i][j] = (r[j] == '.');
            if (a[i][j]) {
                ex = i;
                ey = j;
            }
        }
    }
    tot[cur=0] = 1;
    st[cur][1] = 0;
    f[cur][1] = 1;
    memset(hsh, -1, sizeof hsh);
}

int find(int s) {
    int t = s % P;
    for (; hsh[t] != -1; t = (t + 1) % P) {
        if (st[cur][hsh[t]] == s)
            return hsh[t];
    }
    hsh[t] = ++tot[cur];
    st[cur][hsh[t]] = s;
    f[cur][hsh[t]] = 0;
    return hsh[t];
}

void add(int s, ll val) {
    f[cur][find(s)] += val;
}

void work() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int pre = cur;
            tot[cur ^= 1] = 0;
            for (int k = 1; k <= tot[pre]; k++) {
                int s = st[pre][k];
                ll val = f[pre][k];
                int x = j * 2, y = x + 2;
                int p = (s >> x) & 3, q = (s >> y) & 3;
                int t = s ^ (p << x) ^ (q << y);
                if (!a[i][j]) {
                    add(t, val);
                } else if (!p && !q) {
                    if (a[i+1][j] && a[i][j+1])
                        add(t ^ (1 << x) ^ (2 << y), val);
                } else if (p && q) {
                    if (p == 2 && q == 1) {
                        add(t, val);
                    } else if (p == 1 && q == 2) {
                        if (i == ex && j == ey)
                            ans += val;
                    } else if (p == 1 && q == 1) {
                        int u = y, tmp = 0;
                        do {
                            u += 2;
                            tmp += ((s >> u) & 1) - ((s >> (u+1)) & 1);
                        } while (tmp != -1);
                        add(t ^ (3 << u), val);
                    } else if (p == 2 && q == 2) {
                        int u = x, tmp = 0;
                        do {
                            u -= 2;
                            tmp += ((s >> (u+1)) & 1) - ((s >> u) & 1);
                        } while (tmp != -1);
                        add(t ^ (3 << u), val);
                    }
                } else {
                    if (a[i+1][j])
                        add(t ^ ((p+q) << x), val);
                    if (a[i][j+1])
                        add(t ^ ((p+q) << y), val);
                }
            }
            memset(hsh, -1, sizeof hsh);
        }
        for (int j = 1; j <= tot[cur]; j++)
            st[cur][j] <<= 2;
    }
}

int main() {
    init();
    work();
    printf("%lld\n", ans);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论