题意：
给一个迷宫，求左下角到右下角的路径数。
分析：
插头dp的模板题，建议先看cdq的论文再看代码，这份代码在模板基础上略微有改动。论文地址http://wenku.baidu.com/view/ed2b3e23482fb4daa58d4b74.html
代码：
#include <iostream>
using namespace std;
const int maxD=16;
const int HASH=10007;
const int STATE=1000024;int N,M;
int maze[maxD][maxD];
int code[maxD];
int ch[maxD];struct HASHMAP
{int head[HASH],next[STATE],size;long long state[STATE],f[STATE];void init(){size=0;f[0]=0;memset(head,-1,sizeof(head));}void push(long long st,long long ans){int h=st%HASH;for(int i=head[h];i!=-1;i=next[i])if(state[i]==st){f[i]+=ans;return ;}state[size]=st;f[size]=ans;next[size]=head[h];head[h]=size++;}
}hm[2];void decode(int *code,int m,long long st)
{for(int i=m;i>=0;--i){code[i]=st&7;st>>=3;}
}long long encode(int *code,int m)
{int cnt=1;memset(ch,-1,sizeof(ch));long long st=0; ch[0]=0;for(int i=0;i<=m;++i){if(ch[code[i]]==-1) ch[code[i]]=cnt++;code[i]=ch[code[i]];st<<=3;st|=code[i];}return st;
}void shift(int *code,int m)
{for(int i=m;i>0;--i) code[i]=code[i-1];code[0]=0;
}void init()
{char str[20];memset(maze,0,sizeof(maze));for(int i=1;i<=N;++i){scanf("%s",str);for(int j=0;j<M;++j)if(str[j]=='.')maze[i][j+1]=1;}
}void dpblank(int i,int j,int cur)
{int k,left,up;for(k=0;k<hm[cur].size;++k){decode(code,M,hm[cur].state[k]);left=code[j-1];up=code[j];if((i==N&&j==1)||(i==N&&j==M)){if((left&&!up)||(!left&&up)){code[j]=code[j-1]=0;if(j==M) shift(code,M);hm[cur^1].push(encode(code,M),hm[cur].f[k]);}else if(left==0&&up==0){if(maze[i][j+1]){code[j-1]=0;code[j]=13;hm[cur^1].push(encode(code,M),hm[cur].f[k]);}}continue; }if(left&&up){if(left!=up){code[j]=code[j-1]=0;for(int t=0;t<=M;++t)if(code[t]==left)code[t]=up;if(j==M) shift(code,M);hm[cur^1].push(encode(code,M),hm[cur].f[k]);}}else if((left&&!up)||(!left&&up)){int t;if(left) t=left;else t=up;if(maze[i][j+1]){code[j-1]=0;code[j]=t;hm[cur^1].push(encode(code,M),hm[cur].f[k]);}if(maze[i+1][j]){code[j-1]=t;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]){code[j-1]=code[j]=13;hm[cur^1].push(encode(code,M),hm[cur].f[k]);}}}
}void dpblock(int i,int j,int cur)
{for(int k=0;k<hm[cur].size;++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;hm[cur].init();hm[cur].push(0,1);for(int i=1;i<=N;++i)for(int j=1;j<=M;++j){hm[cur^1].init();if(maze[i][j]) dpblank(i,j,cur);else dpblock(i,j,cur);cur^=1;}printf("%I64d\n",hm[cur].f[0]);
}int main()
{while(scanf("%d%d",&N,&M)==2){if(N==0&&M==0) break;init();solve();}return 0;
}