题解 P1763 【蓄水池】

· · 题解

题目大意：将1~n*m分别放入n*m的格子矩阵里，其中的一些格子有特殊要求（周围的8个格子都要比它大），问方案数。

解决：从小到大放数，则一个普通格子只有等它周围的特殊格子都放完数了才能放数。在不考虑本题中“.”的格子不能是蓄水池的条件的情况下，我们可以写出如下记忆化搜索的方程式f[k][s]=sum{f[k-1][s’]}。其中sum为求和，k为放到了第几个数，s为蓄水池的放数状态（二进制状压），s’表示由s少放一个蓄水池能达到的状态。最后f[n*m][s全放]即为解。本题n<=4，m<=7，最多只有8个蓄水池，故此解可行。

本题的难点在于“.”的格子不能是蓄水池。我们可以用容斥原理来解决。我们设在原来的基础上又增加了p个蓄水池，若p为奇数，则ans应减去f[n*m][s全放]，否则为加上。由于本题对于蓄水池的限制很足（不能相邻），所以这样的枚举次数不会太多，耗时也不大。

状态压缩记忆化搜索也可以写成搜索（即标程做法），所有测试点均在100ms内解决。


#include <iostream>
using namespace std;

const int maxp = 8;
const int maxs = 1 << maxp;
const int mod = 12345678;
const int maxrow = 4;
const int maxcol = 7;
const int maxn = maxrow * maxcol + 2;

int n, m, ans;
int f[maxs][maxn], x[maxp], y[maxp], tp;
bool use[maxrow][maxcol];
char graph[maxrow][maxcol];

void init() {
    scanf("%d%d\n", &n, &m);
    for (int i = 0; i < n; ++i)
        gets(graph[i]);
}

bool in_range(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

int calc() {
    tp = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (graph[i][j] == 'X') x[tp] = i, y[tp++] = j;
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int s = 0; s < 1 << tp; ++s) {
        memset(use, 1, sizeof(use));
        for (int i = 0; i < tp; ++i)
            if (!(s & (1 << i)))
                for (int dx = -1; dx <= 1; ++dx)
                    for (int dy = -1; dy <= 1; ++dy)
                        if (in_range(x[i] + dx, y[i] + dy)) use[x[i] + dx][y[i] + dy] = 0;

        int cnt = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (use[i][j]) ++cnt;

        for (int i = 0; i <= cnt; ++i)
            if (f[s][i]) {
                f[s][i + 1] = (f[s][i + 1] + f[s][i] * (cnt - i)) % mod;
                for (int j = 0; j < tp; ++j)
                    if (!(s & (1 << j))) f[s | (1 << j)][i + 1] = (f[s | (1 << j)][i + 1] + f[s][i]) % mod;
            }
    }
    return f[(1 << tp) - 1][n * m];
}

void search(int x, int y, int k) {
    if (x >= n) ans = (ans + k * calc()) % mod;
    else if (y >= m) search(x + 1, 0, k);
    else {
        search(x, y + 1, k);
        bool ok = 1;
        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy)
                if (in_range(x + dx, y + dy) && graph[x + dx][y + dy] == 'X')
                    ok = 0;
        if (ok) {
            graph[x][y] = 'X';
            search(x, y + 1, -k);
            graph[x][y] = '.';
        }
    }
}

int solve() {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (graph[i][j] == 'X')
                for (int dx = -1; dx <= 1; ++dx)
                    for (int dy = -1; dy <= 1; ++dy)
                        if ((dx || dy) && in_range(i + dx, j + dy) && graph[i + dx][j + dy] == 'X')
                            return 0;
    ans = 0;
    search(0, 0, 1);
    return (ans + mod) % mod;
}

int main() {
    freopen("mon.in", "r", stdin);
    freopen("mon.out", "w", stdout);

    init();
    printf("%d\n", solve());

    return 0;
}

[/cdec]