因为这玩意没什么好当板子的，就作为题解来写

思路

前人之述备矣。

补充几点：

  • 开始一直以为复杂度是错的，后来写了个暴搜发现长度在 1313 以内的合法串只有 4500045000 左右，完全是够的。

主要注意：

  • “((” 的情况应找最近未被匹配的括号。

代码

#include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
#define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using ll = long long;
char c=' ';
int in(void)
{
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
const int maxn=20,maxk=60012;
int n,m,ex,ey,bs[maxn];
char ch[maxn][maxn];
unordered_map<int,ll>f[2];//#:0 (:1 ):2
ll ans=0;
inline int gt(int num,int tp)
{
    return (num>>(tp<<1))&3;
}
int main()
{
    n=in();m=in();
    fru(i,1,n)
    {
        scanf("%s",ch[i]+1);
        fru(j,1,m)if(ch[i][j]=='.')ex=i,ey=j;
    }
    bs[0]=1;
    fru(i,1,m)
    {
        bs[i]=bs[i-1]<<2;
        // cout<<gt(bs[i],i)<<endl;
    }

    f[0][0]=1;
    short int pr=1,dc=0,d1,d2,tp,tm;
    fru(i,1,n)
    {
        swap(pr,dc);
        f[dc].clear();
        for(auto j:f[pr])if(!gt(j.first,m))f[dc][j.first<<2]+=j.second;
        // cout<<i<<"start-----------------------------------------"<<endl;
        // for(auto p:f[dc])
        // {
        // 	fru(op,0,m)cout<<gt(p.first,op)<<' ';
        // 	cout<<p.second<<endl;
        // }
        fru(j,1,m)
        {
            swap(pr,dc);
            f[dc].clear();
            for(auto k:f[pr])
            {
                d1=gt(k.first,j-1);d2=gt(k.first,j);
                if(ch[i][j]=='*')
                {
                    if(!d1&&!d2)f[dc][k.first]+=k.second;
                }
                else if(!d1&&!d2)f[dc][k.first+bs[j-1]+bs[j]*2]+=k.second;
                else if(!d1&&d2)
                {
                    f[dc][k.first]+=k.second;
                    f[dc][k.first+bs[j-1]*d2-bs[j]*d2]+=k.second;
                }
                else if(d1&&!d2)
                {
                    f[dc][k.first]+=k.second;
                    f[dc][k.first-bs[j-1]*d1+bs[j]*d1]+=k.second;
                }
                else if(d1==1&&d2==1)
                {
                    tp=0;
                    fru(l,j+1,m)
                    {
                        tm=gt(k.first,l);
                        if(tm==1)tp++;
                        else if(tm==2)tp--;
                        if(tp==-1)
                        {
                            f[dc][k.first-bs[j-1]-bs[j]-bs[l]]+=k.second;break;
                        }
                    }
                }
                else if(d1==2&&d2==2)
                {
                    tp=0;
                    frd(l,j-2,0)
                    {
                        tm=gt(k.first,l);
                        if(tm==1)tp++;
                        else if(tm==2)tp--;
                        if(tp==1)
                        {
                            f[dc][k.first-bs[j]*2-bs[j-1]*2+bs[l]]+=k.second;break;
                        }
                    }
                }
                else if(d1==2&&d2==1)f[dc][k.first-bs[j]*1-bs[j-1]*2]+=k.second;
                else if(i==ex&&j==ey&&d1==1&&d2==2&&k.first-bs[j-1]-bs[j]*2==0)ans+=k.second;
            }
            // cout<<i<<' '<<j<<"----------------------------------------------"<<endl;
            // for(auto p:f[dc])
            // {
            // 	fru(op,0,m)cout<<gt(p.first,op)<<' ';
            // 	cout<<p.second<<endl;
            // }
        }
    }
    printf("%lld",ans);
    return 0;
}