题解：P6008 [USACO20JAN] Cave Paintings P

· · 题解

P6008 题解

题目大意：

给定一张 n\times m 的网格图，每个点为石头或空白。操作：将一个空白点改为水，如果最终不产生流动则此方案为一个合法的方案。求满足物理原理的空白部分填充方案数。

题目中的“物理原理”指重力作用以及连通器原理。（重力作用应该没人不会吧）

容易发现上层方块一定支配下层方块，考虑DP。

对于每个块，从下往上，依次处理每一行。 具体地，使用并查集，将当前位置 i,j 与其左右下的位置相连，合并时用 dp 数组记录当前位置的方案数，即两边相乘。合并完后发现在最上面一行的无论哪个位置放水都会流动到下方任意一个联通的格子，所以合并后方案数应加 1。

目标答案为：ans = {\textstyle\prod_{i}}dp_{i}，即所有连通块答案的积。

代码

#include <bits/stdc++.h>

using namespace std;
#define int long long

int n, m;
const int N = 1010;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
int fa[M], dp[M];
bool a[N][N], vis[M];
char ch[N][N];

int dx[5] = {0, -1, 0};
int dy[5] = {1, 0, -1};

inline int Hash(int x, int y){
    return (x - 1) * m + y;
}

inline int find(int x){
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}

inline void merge(int x, int y){
    int xx = find(x);
    int yy = find(y);
    if (xx != yy){
        fa[yy] = xx;
        dp[xx] = (dp[xx] * dp[yy]) % mod;   
    }
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            int k = Hash(i, j);
            fa[k] = k;
            dp[k] = 1;
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> ch[i][j];
            if (ch[i][j] == '#') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    for (int i = n - 1; i > 1; i--){
        for (int j = 2; j < m; j++){
            for (int k = 0; k < 3; k++){
                int xx = i + dx[k];
                int yy = j + dy[k];
                if (a[i][j] || a[xx][yy]) continue;
                merge(Hash(i, j), Hash(xx, yy));
            }
        }
        for (int j = 2; j < m; j++){
            int k = find(Hash(i, j));
            if (vis[k] || a[i][j]) continue;
            vis[k] = 1;
            dp[k] = (dp[k] + 1) % mod;
        }
        for (int j = 2; j < m; j++){
            if (a[i][j]) continue;
            int k = find(Hash(i, j));
            vis[k] = 0;
        }
    }
    int ans = 1;
    for (int i = 2; i < n; i++){
        for (int j = 2; j < m; j++){
            int k = Hash(i, j);
            if (find(k) == k && !a[i][j]){
                ans = (ans * dp[k]) % mod;
            }
        }
    }
    cout << ans;
    return 0;
}