自动搬运

查看原文

来自洛谷，原作者为

	bellmanford 【没有谁会是失败者】

搬运于2025-08-24 22:16:28，当前版本为作者最后更新于2020-03-01 17:26:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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

考虑对于所有水的高度（注：高度是指从下往上的高度）小于等于 $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);
}