URAL/1519

来自"NOCOW"

蛋疼死了，水水状压DP，调我半天，555~

哎哎，不想预处理了，小慢啊。。。

嗯，没关系，反正可以很快AC啦~

#include <iostream>
#include <string>
#include <vector>
#include <ctime>
using namespace std;
typedef long long LL;
const int tot=1<<16,mod=(1<<16)-1;
string s;
vector<string> e;
int n,m,now=0,rx=-1,ry=-1,rand_num;
LL ans=0LL;
struct data
{
    int status;
    LL sum;
    inline void reset()
    {
        status=0;
        sum=0LL;
    }
}f[2][tot],t;
inline int get(const int& status,const int& pos)
{
    return (status>>(m-pos<<1)&3);
}
inline int delta(const int& key,const int& pos)
{
    return (key<<(m-pos<<1));
}
inline int Hash(const int& status)
{
    return ((status^rand_num)&mod);
}
inline bool operator != (const data& a,const data &b)
{
    if ((!a.sum) || (a.status == b.status))
        return false;
    return true;
}
inline void updata(const data& t)
{
    int hash_status=Hash(t.status);
    while (f[now][hash_status] != t)
        hash_status=(hash_status+1&mod);
    f[now][hash_status].status=t.status;
    f[now][hash_status].sum+=t.sum;
}
int main()
{
    srand((unsigned)time(NULL));
    rand_num=rand();
    cin >> n >> m;
    for (int i=0;i<n;++i)
    {
        cin >> s;
        for (int j=0;j<m;++j)
            if (s[j] == '.')
            {
                ry=i;
                rx=j;
            }
        e.push_back(s);
    }
    t.status=0;
    t.sum=1;
    updata(t);
    for (int i=0;i<n;++i)
        for (int j=0;j<m;++j)
        {
            now^=1;
            for (int k=0;k<tot;++k)
                f[now][k].reset();
            for (int k=0;k<tot;++k)
                if (f[now^1][k].sum)
                {
                    t=f[now^1][k];
                    if (!j)  t.status>>=2;
                    int p=get(t.status,j),q=get(t.status,j+1);
                    if (e[i][j] == '*')
                    {
                        t.status=t.status-delta(p,j)-delta(q,j+1);
                        updata(t);
                    }
                    else if ((!p) && (!q))
                    {
                        if ((i < n-1) && (j < m-1))
                            if ((e[i+1][j] == '.') && (e[i][j+1] == '.'))
                            {
                                t.status=t.status+delta(1,j)+delta(2,j+1);
                                updata(t);
                            }
                    }
                    else if ((!p) && q)
                    {
                        if ((j < m-1) && (e[i][j+1] == '.'))  updata(t);
                        if ((i < n-1) && (e[i+1][j] == '.'))
                        {
                            t.status=t.status+delta(q,j)-delta(q,j+1);
                            updata(t);
                        }
                    }
                    else if (p && (!q))
                    {
                        if ((i < n-1) && (e[i+1][j] == '.'))  updata(t);
                        if ((j < m-1) && (e[i][j+1] == '.'))
                        {
                            t.status=t.status-delta(p,j)+delta(p,j+1);
                            updata(t);
                        }
                    }
                    else if ((p == 1) && (q == 1))
                    {
                        int a=0,b=j+1;
                        while (a != 1)
                        {
                            int key=get(t.status,++b);
                            if (key == 1)  --a;
                            else if (key == 2)  ++a;
                        }
                        t.status=t.status-delta(1,j)-delta(1,j+1)-delta(1,b);
                        updata(t);
                    }
                    else if ((p == 1) && (q == 2))
                    {
                        if ((i == ry) && (j == rx))
                            ans+=t.sum;
                    }
                    else if ((p == 2) && (q == 1))
                    {
                        t.status=t.status-delta(2,j)-delta(1,j+1);
                        updata(t);
                    }
                    else if ((p == 2) && (q == 2))
                    {
                        int a=0,b=j;
                        while (a != 1)
                        {
                            int key=get(t.status,--b);
                            if (key == 1)  ++a;
                            else if (key == 2)  --a;
                        }
                        t.status=t.status-delta(2,j)-delta(2,j+1)+delta(1,b);
                        updata(t);
                    }
                }
        }
    cout << ans << endl;
    return 0;
}
//by zzy