「UVa-10572」Black & White 题解

2020-02-24

最后一步判断最为关键, 也最容易想错… 请读者思考如何区分这两种情况.

由于某些原因, 链接指向的其实是 vjudge

毒瘤啊!

其实是常规的插头 DP 维护棋盘格连通性的问题, 第一次见感觉很新鲜, 然后… 就自闭了. = =

题目大意

给定一个部分黑白染色的 $n \times m$ 棋盘, 现在给出两种限制

  1. 任意 $2 \times 2$ 的网格不会全黑或者全白.
  2. 所有黑格四连通, 所有白格四连通.

现在要把所有的棋盘染色, 求满足以上限制的方案数.

题目思路

容易发现这是一道插头 DP / 轮廓线 DP, 我们依次考虑两种限制.

对于题目给定的颜色, 容易发现这个限制很好处理, 只不过是在已染色位置按照给定颜色转移.

对于第一种限制, 容易发现只用记录 “当前转移位置” 的左上棋盘的颜色即可. 这样转移的时候, 抛弃掉引起冲突的颜色就好了.

对于第二种限制, 则需要考虑每个点的连通情况. 考虑在轮廓线步步推进的过程中, 刚开始不连通的区域可能在某处得到连通, 所以在转移当前状态时, 显然不能在要求当前轮廓线一直保持两种颜色四连通的状态.

一开始没看到第二种限制, 整个人傻掉了

那怎么办呢? 考虑加一些状态, 记录当前轮廓线上每个位置所属的连通分量编号. 暂且不考虑如何记录这个编号, 先来考虑记录之后如何转移, 以及正确性.

沿用普通的插头 DP 思路, 对于当前状态, 枚举当前位置要放置的颜色, 排除掉已有颜色, 以及 $2 \times 2$ 方格的限制. 新加入棋盘格的连通分量编号呢? 有两种情况:

  1. 当前棋盘格颜色和左侧 / 上方棋盘格颜色相同

    此种情况可以通过对连通分量编号进行简单合并解决.

  2. 当前棋盘格颜色和上方棋盘格颜色不同

    重点考虑这个情况. 为什么要重点分析? 因为当前棋盘格位置上方的棋盘格即将离开轮廓线, 以后就考虑不到了, 但是题目要求颜色各自是四连通的. 如果直接把她抛弃, 那么就… 人没了. = =

    经过思考可以得出, 在轮廓线上还存在上方棋盘格所对应的连通分量就不需要额外考虑这一点了, 即, 可以直接把这个状态扔掉.

    此时我们在状态中记录黑白两色连通分量个数, 并引入 “钦定选择颜色”. 这样, 转移如下:

    • 如果上方棋盘格颜色所属的连通分量个数 $> 1$, 说明以后没有机会再把这些连通分量连接起来了, 放弃吧

    • 如果上方棋盘格颜色所属的连通分量满足题目限制, 那么把剩下的所有格子涂满, 涂成当前棋盘格颜色就好了.

      注意到这样做的条件为, 剩下未填满的行数小于 $2$, 否则直接填满无法满足限制 1.

现在再来考虑如何记录连通分量的编号. 常用的方法有: 最小表示法, 以及广义括号法. 这里只考虑最小表示法, 虽然另一种方法更快一点…

所谓 “最小表示法”, 就是用字典序最小的方法把所有连通分量重标号, 然后没了. 注意每次都要把状态这样整理一下.

代码实现

参考了刘汝佳先生的实现…

毕竟很少有那样清晰的代码和完整的注释了. = =

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// UVA-10572
// DeP
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 8;
const char ch[] = { 'o', '#' };

int n, m, exist;
map<unsigned, int> f[MAXN][MAXN][2];
char G[MAXN][MAXN+1], Ans[MAXN][MAXN], Now[MAXN][MAXN];

struct State {
    int c[MAXN], g[MAXN], cnt[2], UL, tot;

    State() { memset(this, 0, sizeof *this); }

    // 最小表示法
    inline void Normalize() {
        static int rep[MAXN + 1];
        memset(rep, -1, sizeof rep);
        tot = cnt[0] = cnt[1] = 0;
        for (int i = 0; i < m; ++i) {
            if (rep[g[i]] < 0) rep[g[i]] = tot++, ++cnt[c[i]];
            g[i] = rep[g[i]];
        }
    }

    // 合并: 把 from 对应的连通分量编号改为 to
    inline void merge(int to, int from) {
        if (from == to) return;
        for (int i = 0; i < m; ++i) if (g[i] == from) g[i] = to;
    }

    // 编码: 最大值 + 1 = 16 ^ m = 2 ^ (4 * 8) = 2 ^ 32, 正好 unsigned int
    inline unsigned encode() {
        unsigned ret = 0;
        for (int i = 0; i < m; ++i) ret = ret * 16 + c[i] * 8 + g[i];
        return ret;
    }
};

int dfs(int row, int col, State& S, int limit) {
    if (col == m) ++row, col = 0;
    S.Normalize();
    if (row == n) {
        if (S.cnt[0] > 1 || S.cnt[1] > 1) return 0;
        // 记录方案
        if (!exist) {
            exist = 1;
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j) Ans[i][j] = Now[i][j];
        }
        return 1;
    }
    // 一个剪枝: 如果左边颜色和上方颜色不同, 那么左上角的颜色就不重要了
    if (row > 0 && col > 0 && S.c[col] != S.c[col-1]) S.UL = 0;
    unsigned key;
    // 只在不钦定颜色的情况下记忆化
    if (limit < 0) {
        key = S.encode();
        if (f[row][col][S.UL].count(key) > 0) return f[row][col][S.UL][key];
    }
    int ret = 0;
    for (int t = 0; t < 2; ++t) {
        // 钦定颜色 / 限制 0
        if (limit == (t ^ 1) || G[row][col] == ch[t ^ 1]) continue;
        // 限制 1
        if (row > 0 && col > 0 && S.UL == t && S.c[col] == t && S.c[col-1] == t) continue;
        // 新的状态 !
        State T = S;
        T.c[col] = t, T.UL = S.c[col];
        // 通过考虑左侧和上方状态, 来合并一些连通分量
        T.g[col] = (row > 0 && S.c[col] == t)? S.g[col]: S.tot;
        if (col > 0 && T.c[col-1] == t) T.merge(T.g[col-1], T.g[col]);
        Now[row][col] = ch[t];
        if (row > 0 && S.c[col] == (t ^ 1)) {
            bool none = true;
            for (int i = 0; i < m && none; ++i)
                if (T.g[i] == S.g[col]) none = false;
            if (none) {
                // 注意跳转逻辑: 这些条件满足 / 不满足, 直接向下一颜色进行
                if (S.cnt[t ^ 1] > 1 || n - row > 2) continue;
                ret += dfs(row, col + 1, T, t);
                continue;
            }
        }
        ret += dfs(row, col + 1, T, limit);
    }
    if (limit < 0) f[row][col][S.UL][key] = ret;
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti;
    scanf("%d", &Ti);
    while (Ti--) {
        scanf("%d%d", &n, &m);
        // init
        exist = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                for (int k = 0; k < 2; ++k) f[i][j][k].clear();
        // input
        for (int i = 0; i < n; ++i) scanf("%s", G[i]);
        // dp
        State none; none.Normalize();
        printf("%d\n", dfs(0, 0, none, -1));
        // output
        if (exist) for (int i = 0; i < n; ++i, putchar('\n'))
            for (int j = 0; j < m; ++j) putchar(Ans[i][j]);
        putchar('\n');
    }
    return 0;
}

后记

在 陈丹琦 <基于连通性状态压缩的动态规划问题> 对这一类问题有相当详尽的讲解, 头疼看不懂, 以后再说了 咕咕咕

© 2019-2023 DepletedPrism's Blog - Powered by Hexo - Theme Chan