Cave Paintings P

1~5

$N,M \le 10$，直接暴力即可，这里有很多思路（虽然官方并没有给出）

Ben - I didn't have any solution in mind for the N,M ≤ 10 subtask. It was merely intended to be a small correctness test.

6~15

“这道题如果想对了方向就很简单了。” “有趣的思维题。” “奇怪的联通性 DP...”

首先，理解一下题意，如果在某一高度为 $h$ 的格子放置水，那么只有在其所在连通块内且高度不高于 $h$ 的的格子才会有水流进。至此，我们便得到了本题的核心数据结构——并查集。

其次，此题要求我们计数，因此我们使用动态规划。

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

从下往上，从左往右遍历，每遍历到一个空格，向上、左、右三个方向寻找，如果为空格，则合并连通块并进行转移（乘起来）。

最后，对整张图进行遍历，如果该方格为“祖先”，则乘进答案里，得到答案。

时间复杂度 $O(nm)$

写代码时需要注意的细节(好像都很显然?)：

1.dp数组开long long (不开long long见祖宗！！！)

2.需要先对空格进行一维标记

3.在dp初始化和统计答案时初始化为 1

4.由于整个连通块不选也是一种方案，所以在转移时需要寻找这一层的“祖先”并将答案加1

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

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

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

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

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