uva10572 Black & White

题目描述

一个m×n的网格,有的格子已经染上黑色或白色,现在要求将所有的未染色格子染上黑色或白色,使得满足以下2个限制:

1) 所有的黑色的格子是四连通的,所有的白色格子也是四连通的。

2) 不会有一个2×2的子矩阵的4个格子的颜色全部相同。

求方案总数和其中一组方案。(m, n ≤ 8)

输入格式

输入第一行为数据组数T(T≤100)。每组数据第一行为两个整数m和n(2≤n,m≤8)。以下m行每行包含n个字符,“#”表示黑格,“o”表示白格,“.”表示尚未涂色的格子。

输出格式

对于每组数据,第一行输出方案总数,如果存在一组方案,接下来是任意一组方案。在每组数据之间输出一行空行。

样例输入

4
3 3
o..
.##
...
5 5
..#..
.....
....o
o....
.#...
7 5
.....
..o..
#....
.....
..o..
...#.
o....
2 3
###
oo#
6 8
........
........
........
........
.#......
........

样例输出

4
oo#
o##
oo#
0
176
#####
#ooo#
###oo
#o##o
#oooo
####o
ooooo
1
###
oo#
71582
#ooooooo
#o#####o
#ooooo#o
#o#o#o#o
#######o
#ooooooo

分析

显然是插头dp。

要记录的状态为轮廓线上的颜色、连通性,为了判断$2\times 2$子矩阵颜色是否相同,还要记录$(i-1,j-1)$的颜色。

设当前填$(i,j)$,不合法情况有:

  1. 当前填的颜色与预先填好的不同。

  2. 当前$2\times 2$子矩阵颜色相同

  3. $(i-1,j)$与$(i,j)$颜色不同,且$(i-1,j)$与轮廓线上另一个颜色相同的格子不连通。

  4. $(i-1,j)$与$(i,j)$颜色不同,轮廓线上没有与$(i-1,j)$颜色相同的格子,说明此后填的所有格子都必须与$(i,j)$同色,此时判断剩余格子是否有$2\times 2$子矩阵,若有则不合法。

判完不合法状态,剩下就是插头dp的基本操作了。(其实这题没插头,应该叫轮廓线状压dp。)

代码

连通性用最小表示法表示。

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

const int N = 10;
const int NM = 65;
const int P = 1e5+7;
const int S = 1e4;

int n, m;
char a[N][N];
int hsh[P];
int tot[2];
ll st[2][S];
int f[2][S];
char ansCh[NM][S];
int fpre[NM][S];
int cur;
int bl[N];

void init() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", a[i]);
    tot[cur=0] = 1;
    st[0][1] = 0;
    f[0][1] = 1;
    memset(hsh, -1, sizeof hsh);
    memset(fpre, -1, sizeof fpre);
}

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

void decode(int conn) {
    for (int i = m-1; i >= 0; i--) {
        bl[i] = conn & 7;
        conn >>= 3;
    }
}

int encode() {
    static int t[N];
    int top = 0, rtn = 0;
    memset(t, -1, sizeof t);
    for (int i = 0; i < m; i++) {
        if (t[bl[i]] == -1)
            t[bl[i]] = top++;
        rtn = (rtn << 3) | t[bl[i]];
    }
    return rtn;
}

void dp(int x, int y, int c) {
    int pre = cur ^ 1;
    int pos = x * m + y;
    for (int i = 1; i <= tot[pre]; i++) {
        ll s = st[pre][i];
        int conn = s >> (m+1), clr = s & ((1 << (m+1)) - 1);
        bool u = x ? (clr >> y & 1) == c : 0;
        bool l = y ? (clr >> (y-1) & 1) == c : 0;
        bool lu = x && y ? clr >> m == c : 0;
        decode(conn);

        if (u && l && lu) continue;
        if (x == n-1 && y == m-1 && !u && !l && lu)
            continue;
        if (x && !u) {
            int connCnt = 0, clrCnt = 0;
            for (int j = 0; j < m; j++) {
                if (bl[j] == bl[y])
                    connCnt++;
                if ((clr >> j & 1) == !c)
                    clrCnt++;
            }
            if (connCnt == 1) {
                if (clrCnt > 1)
                    continue;
                if (x < n-1 || y < m-2)
                    continue;
            }
        }

        if (u && l) {
            if (bl[y-1] != bl[y]) {
                int t = bl[y];
                for (int j = 0; j < m; j++) {
                    if (bl[j] == t)
                        bl[j] = bl[y-1];
                }
            }
        } else if (!u && l) {
            bl[y] = bl[y-1];
        } else if (!u && !l) {
            bl[y] = m;
        }
        conn = encode();

        if (clr & 1 << y) clr |= 1 << m;
        else clr &= ~(1 << m);
        if (c) clr |= 1 << y;
        else clr &= ~(1 << y);

        ll nws = conn << (m+1) | clr;
        int t = getId(nws);
        f[cur][t] += f[pre][i];
        if (fpre[pos][t] == -1) {
            fpre[pos][t] = i;
            ansCh[pos][t] = c ? '#' : 'o';
        }
    }
}

void print(int t) {
    for (int i = n-1; i >= 0; i--) {
        for (int j = m-1; j >= 0; j--) {
            int u = i * m + j;
            a[i][j] = ansCh[u][t];
            t = fpre[u][t];
        }
    }
    for (int i = 0; i < n; i++)
        puts(a[i]);
}

void work() {
    init();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tot[cur^=1] = 0;
            if (a[i][j] != '#')
                dp(i, j, 0);
            if (a[i][j] != 'o')
                dp(i, j, 1);
            memset(hsh, -1, sizeof hsh);
        }
    }

    int ans = 0, t;
    for (int i = 1; i <= tot[cur]; i++) {
        int s = st[cur][i];
        int conn = s >> (m+1);
        decode(conn);
        int mx = 0;
        for (int j = 0; j < m; j++)
            mx = std::max(mx, bl[j]);
        if (mx > 1) continue;
        ans += f[cur][i];
        t = i;
    }
    printf("%d\n", ans);
    if (ans > 0) print(t);
    puts("");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论