C++(clang++ 11.0.1) 解法, 执行用时: 115ms, 内存消耗: 5796K, 提交时间: 2022-12-11 15:10:44

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int P=20110520;
ll p4[15];
int a[105][15]={0};
ll bit[2][300000],val[2][300000];
int head[300000],nex[300000];
int tot[300000];
int n,m;
void insert(ll b,ll v,int now)
{
    int tmp=b%299987;
    for(int i=head[tmp];i;i=nex[i])
        if(bit[now][i]==b) {val[now][i]=(val[now][i]+v)%P;return;}
    nex[++tot[now]]=head[tmp];
    head[tmp]=tot[now];
    bit[now][tot[now]]=b;
    val[now][tot[now]]=v%P;
}
void solve(){
    int pre=0,now=1;
    tot[now]=1;
    bit[now][1]=0;
    val[now][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=tot[now];j++)
            bit[now][j]<<=2;
        for(int j=1;j<=m;j++){
            memset(head,0,sizeof(head));
            swap(pre,now);
            tot[now]=0;
            for(int k=1;k<=tot[pre];k++)
            {
                ll b=bit[pre][k],v=val[pre][k];
                ll b1=(b>>(2*(j-1)))%4;
                ll b2=(b>>(2*j))%4;
                if(!a[i][j]) {
                    if(!b1&&!b2) insert(b,v,now);  
                    
                }
                else if(b1==1&&b2==1) insert(b-p4[j-1]-p4[j],v,now);
                else if(!b1&&!b2) {
                    if(a[i][j+1]&&a[i+1][j]) insert(b+2*p4[j-1]+2*p4[j],v,now);
                    if(a[i][j+1]) insert(b+p4[j],v,now);
                    if(a[i+1][j]) insert(b+p4[j-1],v,now);
                }
                else if(!b1&&b2==1){
                    if(a[i][j+1]) insert(b+p4[j],v,now);
                    if(a[i+1][j]) insert(b-p4[j]+p4[j-1],v,now);
                }
                else if(!b1&&b2==2){
                    insert(b-p4[j]*2,v,now);
                    if(a[i+1][j]) insert(b-2*p4[j]+2*p4[j-1],v,now);
                }
                else if(b1==1&&!b2){
                    if(a[i][j+1]) insert(b-p4[j-1]+p4[j],v,now);
                    if(a[i+1][j]) insert(b+p4[j-1],v,now);
                }
                else if(b1==1&&b2==1){
                    insert(b-p4[j-1]-p4[j],v,now);
                }
                else if(b1==2&&!b2){
                    if(a[i][j+1]) insert(b-2*p4[j-1]+2*p4[j],v,now);
                    insert(b-2*p4[j-1],v,now);
                }
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=tot[now];i++)
        ans=(ans+val[now][i])%P;
    printf("%lld\n",ans);
}
int main(void){
    //freopen("C:\\Users\\86155\\Desktop\\1.in","r",stdin);
    //freopen("C:\\Users\\86155\\Desktop\\1.out","w",stdout);
    p4[0]=1;
    for(int i=1;i<15;i++) p4[i]=p4[i-1]<<2;
    scanf("%d%d",&n,&m);
    if(n<m){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                char tmp=getchar();
                while(tmp!='_'&&tmp!='*') tmp=getchar();
                if(tmp=='_') a[j][i]=1;
            }
        swap(n,m);
    }
    else {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                char tmp=getchar();
                while(tmp!='_'&&tmp!='*') tmp=getchar();
                if(tmp=='_') a[i][j]=1;
                //printf("%d\n",a[i][j]);
            }
    }
    solve();
}