学步园

被这题卡了一整天，测试无数的数据，和对拍数据无误，几乎崩溃，后来重新敲时，发现自身写法的漏洞，果不其然，就是这个潜伏多年的bug，在ural，poj，以及我的vim下得出的数据都是一样的，我现在有些明白，为什么以前出现过在G++AC的题目，到C++是wa，应该是写法上的漏洞，编译器不同结果是不同的，改完这个bug，就AC了，rank排到第一去了。

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#define LL int
using namespace std;
const int maxn=30001,mod=1000000007;
int mov[14]={0,2,4,6,8,10,12,14,16,18,20,22,24,26};
struct node
{
    int size,head[maxn],next[maxn];
    LL sta[maxn],sum[maxn];
    void clear()
    {
        memset(head,-1,sizeof(head));
        size=0;
    }
    void push(LL st,const LL v)
    {
        LL hash=st%maxn;
        for(int i=head[hash];i>=0;i=next[i])
        {
            if(sta[i]==st)
            {
                sum[i]+=v;
                if(sum[i]>=mod)
                    sum[i]-=mod;
                return ;
            }
        }
        sta[size]=st,sum[size]=v;
        next[size]=head[hash],head[hash]=size++;
    }
}dp[2][37];
inline LL getbit(LL st,int k){return 3&(st>>mov[k]);}
inline LL pybit(LL st,int k){return st<<mov[k];}
inline LL clrbit(LL st,int a,int b){return st&(~(3<<mov[a]))&(~(3<<mov[b]));}
inline LL fl(LL st,int k,int n)
{
    int cnt=1;
    for(int i=k+1;i<=n;i++)
    {
        LL e=getbit(st,i);
        if(e==2) cnt--;
        else if(e==1) cnt++;
        if(cnt==0) return i;
    }
}
inline LL fr(LL st,int k)
{
    int cnt=1;
    for(int i=k-1;i>=0;i--)
    {
        LL e=getbit(st,i);
        if(e==2) cnt++;
        else if(e==1) cnt--;
        if(cnt==0) return i;
    }
}
inline LL count(LL st,int k)
{
    int cnt=0;
    for(int i=k-1;i>=0;i--)
    {
        if(getbit(st,i))
            cnt++;
    }
    return cnt;
}
int n,m,c,sx,sy;
char gp[20][20];
void tran(int &pre,int &now,bool flag)
{
    pre=now,now^=1;
    for(int j=0;j<=c;j++)
        dp[now][j].clear();
    if(flag)
    {
        for(int j=0;j<=c;j++)
            for(int k=0;k<dp[pre][j].size;k++)
                dp[now][j].push(dp[pre][j].sta[k]<<2,dp[pre][j].sum[k]);
    }
}
LL DP()
{
    int now=1,pre=0;
    tran(pre,now,0);
    dp[0][0].push(0,1);
    for(int i=1;i<=n;i++)
    {
        if(i>sx)break;
        tran(pre,now,1);
        for(int j=1;j<=m;j++)
        {
            if(i==sx&&j>sy)break;
            tran(pre,now,0);
            for(int k=0;k<c;k++)
            {
                for(int x=0;x<dp[pre][k].size;x++)
                {
                    LL l=getbit(dp[pre][k].sta[x],j-1);
                    LL up=getbit(dp[pre][k].sta[x],j);
                    LL st=clrbit(dp[pre][k].sta[x],j,j-1);
                    if(!l&&!up)
                    {
                        if(gp[i][j]=='*')
                            dp[now][k].push(st,dp[pre][k].sum[x]);
                        else if(i<n&&j<m&&gp[i+1][j]=='.'&&gp[i][j+1]=='.')
                            dp[now][k].push(st|pybit(1,j-1)|pybit(2,j),dp[pre][k].sum[x]);
                    }
                    else if(!l||!up)
                    {
                        int e=l==0?up:l;
                        if(i<n&&gp[i+1][j]=='.') dp[now][k].push(st|pybit(e,j-1),dp[pre][k].sum[x]);
                        if(j<m&&gp[i][j+1]=='.') dp[now][k].push(st|pybit(e,j),dp[pre][k].sum[x]);
                    }
                    else if(l==1&&up==1)
                        dp[now][k].push(st^pybit(3,fl(st,j,m)),dp[pre][k].sum[x]);
                    else if(l==2&&up==2)
                        dp[now][k].push(st^pybit(3,fr(st,j-1)),dp[pre][k].sum[x]);
                    else if(l==2&&up==1)
                        dp[now][k].push(st,dp[pre][k].sum[x]);
                    else if((count(st,j-1)&1)==0)dp[now][k+1].push(st,dp[pre][k].sum[x]);

                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<dp[now][c].size;i++)
        if(dp[now][c].sta[i]==0)
            ans+=dp[now][c].sum[i];
    return ans;
}
int main()
{
    int t,T=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&c);
        for(int i=1;i<=n;i++)
            scanf("%s",&gp[i][1]);
        bool flag=0;
        for(int i=n;i>=1&&!flag;i--)
        {
            for(int j=m;j>=1&&!flag;j--)
                if(gp[i][j]=='.')
                    flag=1,sx=i,sy=j;
        }
        if(!flag)
        {
            if(c==0)
                puts("1");
            else puts("0");
        }
        else if(c>(n*m)/4||(flag&&c==0)) puts("0");
        else cout<< DP()<<'\n';
    }
    return 0;
}