题解 P6008 【[USACO20JAN]Cave Paintings P】

· · 题解

这道题如果想对了方向就很简单了。

可如果像我一样一直在想如何把图给抠出一个森林就很难了。

发现如果一个格子放了水，对于在这个格子及以下的高度只要有一条路径能到达另一个格子，那那个格子也会有水。

不难联想到可以将各个点标上号，使用并查集来做此题。

考虑对于所有水的高度（注：高度是指从下往上的高度）小于等于 h 的方案数，答案应该是所有联通块的方案数的乘积。

可以发现，如果有两个联通块合并，更新的答案应该是这两个联通快的方案数的乘积。

所以对于原先高度为 h 的各个联通块的方案数，可以遍历一遍第 h+1 行，看有哪些联通块可以合并，然后将方案数更新，由于如果在第 h+1 行放一格水，这一个联通快就都会充满水，所以还需将更新完的各个联通块的方案数加一。

那么就可以每次更新联通块，从高度为 h 推到高度为 h+1 了。

为了方便可以将方案数存在祖先那里，然后从第 n 行一直推到第 1 行了。

总效率 O(nm) 。

#include<iostream>
#include<cstdio>
using namespace std;

#define int long long
#define num(i,j) ((i-1)*m+j)
const int M=1e3+5,JYY=1e9+7;

int n,m,ans=1,fa[M*M],dp[M*M],Map[M][M];
int nxt[3][2]={{1,0},{0,1},{0,-1}};
bool vis[M*M];
char s[M];

int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') y=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*y;
}

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

void unionn(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy) fa[fx]=fy,dp[fy]=(dp[fy]*dp[fx])%JYY;
}

signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) fa[num(i,j)]=num(i,j),dp[num(i,j)]=1;
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            if(s[j]=='#') Map[i][j]=1;
            else Map[i][j]=0;
        }
    }
    for(int i=n-1;i>=2;i--){
        for(int j=2;j<=m-1;j++){
            if(Map[i][j]) continue;
            for(int k=0;k<3;k++){
                int nx=i+nxt[k][0],ny=j+nxt[k][1];
                if(!Map[nx][ny]) unionn(num(i,j),num(nx,ny));
            }
        }
        for(int j=2;j<=m-1;j++){
            if(Map[i][j]) continue;
            int f=find(num(i,j));
            if(vis[f]) continue;
            vis[f]=1;dp[f]=(dp[f]+1)%JYY;
        }
        for(int j=2;j<=m-1;j++){
            if(Map[i][j]) continue;
            int f=find(num(i,j));
            vis[f]=0;
        }
    }
    for(int i=2;i<=n-1;i++){
        for(int j=2;j<=m-1;j++){
            if(Map[i][j]) continue;
            if(fa[num(i,j)]==num(i,j)){
                ans=(ans*dp[num(i,j)])%JYY;
            }
        }
    }
    printf("%lld\n",ans);
}