学步园

2 2
..
..
2 3
#..
...
3 4
....
....
....
0 0

1
1
4

         这题和Ural  1519  Formula 1类似。只是把回路换成以左下角作为起点。右下角换成终点的回路数而已。所以预处理加两行就行。

比如：

3    4                     . . . .

. . . .                      . . . .

. . . .    ---------->    . . . .

. . . .                       . ##.

                              . . . .

这样预处理后就和那题一样了。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

const int HASH=30007;//哈希表的大小
const int STATE=1000010;//状态数
const int MAXD=15;
int N,M,ex,ey;//ex,ey最后一个可到点
int code[MAXD],maze[MAXD][MAXD],mcod[MAXD];//编码。和存地图。最小表示法
char s[20];

struct HASHMAP//哈希表结构
{
    int head[HASH],next[STATE],sz;//哈希表头指针模数相同的状态用链表连接。方便状态查找和判重
    long long f[STATE],state[STATE];//f记录对应状态的方法数。next指向模数相同的下一个状态。state记录状态。sz记录状态总数
    void init()//哈希表初始化函数
    {
        sz=0;
        memset(head,-1,sizeof(head));
    }
    void push(long long st,long long ans)//压入状态和方法数
    {
        int i,h=st%HASH;
        for(i=head[h]; i!=-1; i=next[i])
            if(st==state[i])//若状态已经存在。方法数增加就行
            {
                f[i]+=ans;
                return;
            }
        f[sz]=ans;//存入新的可行状态
        state[sz]=st;
        next[sz]=head[h];
        head[h]=sz++;
    }
} hm[2];

void decode(int *code,int m,long long st)//编码从高位到低位m到0编码。对应从左到右的插头
{
    int i;
    for(i=m; i>=0; i--)
    {
        code[i]=st&7;
        st>>=3;
    }
}
long long encode(int *code,int m)//最小表示法解码到st中
{
    int i,cnt=1;
    long long st=0;
    memset(mcod,-1,sizeof mcod);
    mcod[0]=0;
    for( i=0; i<=m; i++)
    {
        if(mcod[code[i]]==-1)
            mcod[code[i]]=cnt++;
        code[i]=mcod[code[i]];
        st<<=3;
        st|=code[i];
    }
    return st;
}
void init()//读数据。初始化
{
    int i,j;
    memset(maze,0,sizeof maze);
    ex=0;
    for(i=1; i<=N; i++)
    {
        scanf("%s",s+1);
        for( j=1; j<=M; j++)
            if(s[j]=='.')
                maze[i][j]=1;
    }
    maze[N+1][1]=maze[N+1][M]=1;
    for(i=2;i<M;i++)
        maze[N+1][i]=0;
    for(i=1;i<=M;i++)
        maze[N+2][i]=1;
    N+=2;
    ex=N,ey=M;
}

void shift(int *code,int m)//换行的时候移位
{
    int i;
    for(i=m; i>0; i--)
        code[i]=code[i-1];
    code[0]=0;
}

void dpblank(int i,int j,int cur)//处理可到格的情况
{
    int k,t,left,up,temp;
    for(k=0; k<hm[cur].sz; k++) //遍历j格出轮廓线的状态进行状态转移
    {
        decode(code,M,hm[cur].state[k]);//对状态进行编码
        left=code[j-1];//获取左插头状态
        up=code[j];//获取上插头状态
        if(left&&up)//11  -> 00
        {
            if(left==up)//形成回路
            {
                if(i==ex&&j==ey)//判断是否到了最后一个可到点
                {
                    code[j-1]=code[j]=0;//只能为0一个格子只能两个插头
                    if(j==M)shift(code,M);//到了边界后换行
                    hm[cur^1].push(encode(code,M),hm[cur].f[k]);//压入新状态
                }
            }
            else
            {
                code[j-1]=code[j]=0;
                for(t=0;t<=M;t++)
                    if(code[t]==up)
                {
                    code[t]=left;
                    break;
                }
                if(j==M)shift(code,M);//到了边界后换行
                hm[cur^1].push(encode(code,M),hm[cur].f[k]);//压入新状态
            }
        }
        else if((!left&&up)||(left&&!up))//01 或 10
        {
            if(up)
                temp=up;
            else
                temp=left;
            if(maze[i][j+1])//j==m时maze[i][j]为0也不用shift
            {
                code[j-1]=0;
                code[j]=temp;
                hm[cur^1].push(encode(code,M),hm[cur].f[k]);
            }
            if(maze[i+1][j])
            {
                code[j-1]=temp;
                code[j]=0;
                if(j==M)shift(code,M);//这个不要忘了！
                hm[cur^1].push(encode(code,M),hm[cur].f[k]);
            }
        }
        else
        {
            if(maze[i][j+1]&&maze[i+1][j])//若j==m不会合法所以不用shift
            {
                code[j]=code[j-1]=13;
                hm[cur^1].push(encode(code,M),hm[cur].f[k]);
            }
        }
    }
}

void dpblock(int i,int j,int cur)//处理不能到格的情况
{
    int k;
    for(k=0; k<hm[cur].sz; k++) //存入状态均合法不用判断
    {
        decode(code,M,hm[cur].state[k]);//先编码
        code[j-1]=code[j]=0;//肯定不能用插头
        if(j==M)shift(code,M);//转移到下一行
        hm[cur^1].push(encode(code,M),hm[cur].f[k]);
    }
}

void solve()
{
    int i,j,cur=0;
    long long ans=0;
    hm[cur].init();//cur用于滚动数组。节约空间。cur存当前格上插头和左插头情况。cur^1用于记录转移出的新状态即下一格
    hm[cur].push(0,1);
    for(i=1; i<=N; i++)
        for(j=1; j<=M; j++)
        {
            hm[cur^1].init();//初始化
            if(maze[i][j])dpblank(i,j,cur);
            else dpblock(i,j,cur);
            cur^=1;
        }
    for(i=0; i<hm[cur].sz; i++)
        ans+=hm[cur].f[i];
    printf("%I64d\n",ans);
}
int main()
{
    while(scanf("%d%d",&N,&M),N||M)
    {
        init();
        if(!ex)
            printf("0\n");
        else
            solve();
    }
    return 0;
}