ural1519

题解：

插头ｄｐ

具体可以看看ｃｄｑ论文

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=128483;
int n,m,ex,ey;
char s[15][15];
struct node
{
    int H[N],tot,st[N];
    ll s[N];
    void init()
     {
        memset(H,255,sizeof(H));
        tot=0;
     }
    void add(int S,ll v)
     {
        int i=S%N;
        for (;H[i]>=0&&st[H[i]]!=S;i=(i+1)%N);
        if (H[i]<0)
         {
            st[tot]=S;
            s[tot]=v;
            H[i]=tot++;
         }
        else s[H[i]]+=v;
     } 
}f[2];
int Get(int x,int y)
{
    return (x>>(y<<1))&3;
}
int Set(int &z,int x,int y)
{
    z^=Get(z,x)<<(x<<1);
    z^=y<<(x<<1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
     {
         scanf("%s",s[i]);
         for (int j=0;j<m;j++)
          if (s[i][j]=='.')
           {
               ex=i;
               ey=j;
           }
     }
    int p=0,q=1;
    f[p].s[0]=1; f[p].tot=1;
    for (int i=0;i<n;i++)
     {
        for (int j=0;j<m;j++,p^=1,q^=1)
         {
            f[q].init();
            if (s[i][j]=='*')
             {
                for (int k=0;k<f[p].tot;k++)
                 {
                    int st=f[p].st[k]; 
                    ll s=f[p].s[k];
                    if (!Get(st,j)&&!Get(st,j+1))f[q].add(st,s);
                 }
                continue;
             }
            for (int k=0;k<f[p].tot;k++)
             {
                int st=f[p].st[k],x=Get(st,j),y=Get(st,j+1);
                ll s=f[p].s[k];
                if (!x)
                 {
                    if (!y)
                     {
                        if (j==m-1) continue;
                        Set(st,j,1); Set(st,j+1,2);
                        f[q].add(st,s);
                     }
                    else
                     {
                        if (j<m-1) f[q].add(st,s);
                        Set(st,j+1,0); Set(st,j,y);
                        f[q].add(st,s);
                     }
                 }
                else if (!y)
                 {
                    f[q].add(st,s);
                    if (j==m-1) continue;
                    Set(st,j,0); Set(st,j+1,x);
                    f[q].add(st,s);
                 }
                else
                 {
                    Set(st,j,0); Set(st,j+1,0);
                    if (x==1)
                     {
                        if (y==1)
                        {
                            for (int k=j+2,t=1;;k++)
                             {
                                if (Get(st,k)==1) t++;
                                else if (Get(st,k)==2)
                                 {
                                    t--;
                                    if (!t)
                                     {
                                        Set(st,k,1);
                                        f[q].add(st,s);
                                        break;
                                     }
                                 }
                             }
                         }
                        else if (i==ex && j==ey) f[q].add(st,s);
                     }
                    else
                     {
                        if (y==1) f[q].add(st,s);else
                         {
                            for (int k=j-1,t=1;;k--)
                             {
                                if (Get(st,k)==2) t++;
                                else if (Get(st,k)==1)
                                 {
                                    t--;
                                    if (!t)
                                     {
                                        Set(st,k,2);
                                        f[q].add(st,s);
                                        break;
                                     }
                                 }
                             }
                         }
                     }
                 }
             }
         }
        for (int j=0;j<f[p].tot;j++) f[p].st[j]<<=2;
     }
    for (int i=0;i<f[p].tot;i++)
     if (f[p].st[i]==0)
      {
          printf("%lld
",f[p].s[i]);
          return 0;
      } 
    puts("0");
    return 0; 
}