洛谷：Link（所有点输出0）

loj：Link

code:

//
// Created by swift on 2020/7/17.
//
#include<bits/stdc++.h>
using namespace std;
int n,m;
#define MOD 299993
#define int long long
struct HASH{
    int sta[2],dp[2];//状态和dp值
}mp[8000000];//哈希表
int nxt[8000000];
int head[400000];
int x;
int cnt[2];
int in[101][101];

struct sta{
    int a[20];
};//状态
sta pack(int a){
    sta tmp;
    tmp.a[0]=a&3;
    for(int i=1;i<=m;i++){
        tmp.a[i]=(a>>(i<<1))&3;
    }
    return tmp;
}//状态加密
int unpack(sta a){
    int tmp=0;
    tmp|=a.a[0];
    for(int i=1;i<=m;i++){
        tmp|=(a.a[i]<<(i<<1));
    }
    return tmp;
}//状态解密
namespace DEBUG{
    void print(sta a){
        for(int i=0;i<=m;i++){
            cout<<a.a[i]<<" ";
        }
        cout<<endl;
    }
}
void ins(int sta,int v){
    /*cout<<"ins:"<<endl;
    DEBUG::print(pack(sta));
    cout<<":ins"<<endl;*/
    v%=20110520;
    int idx=sta%MOD;
    //cout<<idx<<" "<<cnt[x]<<endl;
    for(int i=head[idx];i;i=nxt[i]){
        //cout<<"#"<<i<<endl;
        if(mp[i].sta[x]==sta){
            mp[i].dp[x]+=v;//已有此状态
            mp[i].dp[x]%=20110520;
            return;
        }
    }
    cnt[x]++;//没有，新建状态
    mp[cnt[x]].sta[x]=sta;
    mp[cnt[x]].dp[x]=v;
    nxt[cnt[x]]=head[idx];
    head[idx]=cnt[x];
}
int lx,ly,ans;
void solve(){
    ins(0,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            memset(head,0,sizeof(head));
            int lst=x;
            /*cout<<"NOW_TOT "<<cnt[x]<<endl;
            cout<<"begin:"<<endl;
            for(int k=1;k<=cnt[x];k++){
                DEBUG::print(pack(mp[k].sta[x]));
            }
            cout<<":end"<<endl;*/
            x^=1;
            cnt[x]=0;
            for(int k=1;k<=cnt[lst];k++){
                sta now=pack(mp[k].sta[lst]),tmp=now;
                int v=mp[k].dp[lst];
                int l=now.a[0],o=now.a[j];
                if(!in[i][j]){
                    if(!l&&!o)
                    ins(unpack(tmp),v);
                }
                else {
                    if (o == 0 && l == 0) {
                        tmp.a[0] = 1;
                        if(in[i][j+1])
                        ins(unpack(tmp), v);
                        tmp = now;
                        tmp.a[j] = 1;
                        if(in[i+1][j])
                        ins(unpack(tmp), v);
                        tmp = now;
                        tmp.a[j] = tmp.a[0] = 2;
                        if(in[i][j+1]&&in[i+1][j])
                        ins(unpack(tmp), v);
                    }
                    if (o == 1 && l == 1) {
                        if(i==lx&&j==ly){
                            ans+=v;
                            ans%=20110520;
                        }
                        tmp.a[0] = tmp.a[j] = 0;
                        ins(unpack(tmp), v);
                        tmp = now;
                    }
                    if (o == 1 && l == 0) {
                        if(in[i+1][j])
                        ins(unpack(tmp), v);
                        tmp = now;
                        tmp.a[0] = 2;
                        tmp.a[j] = 0;
                        if(in[i][j+1])
                        ins(unpack(tmp), v);
                    }
                    if (o == 0 && l == 1) {
                        if(in[i][j+1])
                        ins(unpack(tmp), v);
                        tmp = now;
                        tmp.a[0] = 0;
                        tmp.a[j] = 2;
                        if(in[i+1][j])
                        ins(unpack(tmp), v);
                    }
                    if (o == 2 && l == 0) {
                        if(in[i+1][j])
                        ins(unpack(tmp), v);
                        tmp.a[j] = 0;
                        ins(unpack(tmp), v);
                        if (i == lx && j == ly) {
                            ans += v;
                            ans%=20110520;
                        }
                    }
                    if (o == 0 && l == 2) {
                        if(in[i][j+1])
                        ins(unpack(tmp), v);
                        tmp.a[0] = 0;
                        ins(unpack(tmp), v);
                        if (i == lx && j == ly) {
                            ans += v;
                            ans%=20110520;
                        }
                    }
                }
                //DEBUG::print(now);
                //cout<<i<<" "<<j<<endl;
            }
        }
    printf("%lld\n",ans);
}
signed main(){
    scanf("%lld%lld",&n,&m);
    /*for(int i=0;i<=100;i++)
        for(int j=0;j<=100;j++){
            in[i][j]=1;
        }*/
    if(m>n) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                char c = getchar();
                while (c != '*' && c != '_')c = getchar();
                in[j][i] = (c == '_');
                if (in[j][i]) {
                    lx = j;
                    ly = i;
                }
            }
        swap(n, m);
    }
    else{
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                char c = getchar();
                while (c != '*' && c != '_')c = getchar();
                in[i][j] = (c == '_');
                if (in[i][j]) {
                    lx = i;
                    ly = j;
                }
            }

    }
    solve();
    return 0;
}