Link
用并查集把每一行在同一个连通块内的点并起来，并向下一行的与当前连通块有交的连通块连边。
这样会构成一棵森林的结构，然后直接dp即可。
#include <cstdio>
using i64=long long;
const int N=1007,P=1000000007;
int id[N][N],fa[N*N];i64 f[N*N];char str[N][N];
int find(int x){return x==fa[x]? x:fa[x]=find(fa[x]);}
int main()
{
int n,m,cnt=0;i64 ans=1;scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%s",str[i]+1);
for(int i=n-1;i>1;--i)
{
int now=cnt;
for(int j=2,k;j<m;++j)
if(str[i][j]==‘.‘)
{
if(str[i][j-1]==‘#‘) f[++cnt]=1,fa[cnt]=cnt;
if(id[i][j]=cnt,str[i+1][j]==‘.‘) if((k=find(id[i+1][j]))!=cnt) (f[cnt]*=f[k])%=P,fa[k]=cnt;
}
for(int j=now+1;j<=cnt;++j) if(find(j)==j) ++f[j];
}
for(int i=1;i<=cnt;++i) if(find(i)==i) (ans*=f[i])%=P;
printf("%lld",ans);
}
LOJ3246 「USACO 2020.1 Platinum」Cave Paintings
原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/13097341.html