题解

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
 
char grid[1005][1005];
 
int uf[1005][1005];
int up[1005][1005];
int id[1005][1005];
 
vector<int> children[1005*1005];
int tree_size=1;
 
int dp[1005*1005];
 
int find(int layer,int a){
	while(uf[layer][a]!=a){
		a=uf[layer][a]=uf[layer][uf[layer][a]];
	}
	return a;
}
 
void merge(int layer,int a,int b){
	a=find(layer,a),b=find(layer,b);
	uf[layer][a]=b;
}
 
void pull(int i){
	dp[i]=1;
	for(int j:children[i]){
		dp[i]=1LL*dp[i]*dp[j]%MOD;
	}
	dp[i]++;
}
 
int main(){
	int N,M;
	scanf("%d %d",&N,&M); // scanf加速！
	for(int i=0;i<N;i++){
		scanf("%s",grid[i]);
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			uf[i][j]=j;
		}
	}
	memset(up,-1,sizeof up);
	for(int i=N-1;i>=0;i--){
		for(int j=0;j<M;j++){
			uf[i][j]=j;
		}
		
		for(int j=0;j+1<M;j++){
			if(grid[i][j]=='.'&&grid[i][j+1]=='.'){
		 		merge(i,j,j+1);
			}
		}
		if(i<N-1){
			for(int j=0;j<M;j++){
				if(grid[i][j]=='.'&&grid[i+1][j]=='.'){
					if(up[i+1][find(i+1,j)]==-1){
						up[i+1][find(i+1,j)]=j;
					}else{
						merge(i,j,up[i+1][find(i+1,j)]);
					}
				}
			}
		}
	}
	for(int i=N-1;i>=0;i--){
		for(int j=0;j<M;j++){
			if(grid[i][j]=='.'&&find(i,j)==j){
				id[i][j]=tree_size++;
			}
		}
	}
	for(int i=N-1;i>=0;i--){
		for(int j=0;j<M;j++){
			if(grid[i][j]=='.'&&find(i,j)==j){
				if(up[i][j]!=-1){
					children[id[i-1][find(i-1,up[i][j])]].push_back(id[i][j]);
				}else{
					children[0].push_back(id[i][j]);
				}
			}
		}
	}
	for(int i=1;i<tree_size;i++){
		pull(i);
	}
	pull(0);
	cout<<(dp[0]+MOD-1)%MOD;
}