【poj1739】 Tony's Tour

// poj1739
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define MOD 4001
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;

const int maxd=15,maxs=100010,maxh=4010;
int head[maxh],next[maxs];
int n,m,code[maxd],t[maxd],a[maxd][maxd],size[2];
char ch[maxd];
LL s[2][maxs],tot[2][maxs];

void decode(LL st) {   //解码
	for (int i=m;i>=0;i--) {
		code[i]=st&7;
		st>>=3;
	}
}
LL encode() {   //编码
	int cnt=0;
	memset(t,-1,sizeof(t));
	t[0]=0;
	LL st=0;
	for (int i=0;i<=m;i++) {
		if (t[code[i]]==-1) t[code[i]]=++cnt;
		code[i]=t[code[i]];
		st<<=3;st|=code[i];
	}
	return st;
}
void shift() {   //换行
	for (int i=m;i;i--) code[i]=code[i-1];
	code[0]=0;
}
void add(int p,LL num) {   //更新hash表
	LL tmp=encode();
	LL id=tmp%MOD;
	for (int i=head[id];i;i=next[i]) 
		if (s[p][i]==tmp) {tot[p][i]+=num;return;}
	next[++size[p]]=head[id];s[p][size[p]]=tmp;tot[p][size[p]]=num;
	head[id]=size[p];
}
void Init() {
	memset(head,0,sizeof(head));
	memset(size,0,sizeof(size));
	memset(tot,0,sizeof(tot));
	memset(s,0,sizeof(s));
	memset(a,0,sizeof(a));
}
int main() {
	while (scanf("%d%d",&n,&m)!=EOF && n && m) {
		Init();
		for (int i=1;i<=n;i++) {
			scanf("%s",ch+1);
			for (int j=1;j<=m;j++) a[i][j]=ch[j]==‘.‘;
		}
		a[n+1][1]=a[n+1][m]=1;
		for (int i=1;i<=m;i++) a[n+2][i]=1;
		n+=2;   //加行
		int ex=n,ey=m;   //终止格显然是无障碍的

		int p=0;
		tot[0][1]=1;size[0]=1;s[0][1]=0;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++) {
				p^=1;   //滚动
				size[p]=0;
				memset(head,0,sizeof(head));   //清空hash表
				for (int k=1;k<=size[p^1];k++) {
					decode(s[p^1][k]);   //解码
					int left=code[j-1],up=code[j];   //左插头，上插头
					if (!a[i][j]) {   //该格子为障碍格
						code[j-1]=code[j]=0;
						if (j==m) shift();
						add(p,tot[p^1][k]);
						continue;
					}
					if (left && up) {   //左、上插头都存在，合并连通块
						if (left==up) {   //即将合并的两部分在同一个联通分量中
							if (i==ex && j==ey) {   //只能出现在最后一个格子
								code[j]=code[j-1]=0;
								if (j==m) shift();
								add(p,tot[p^1][k]);
							}
						}
						else {   //不在同一个联通分量，合并
							code[j-1]=code[j]=0;
							for (int l=0;l<=m;l++) if (code[l]==left) code[l]=up;
							if (j==m) shift();
							add(p,tot[p^1][k]);
						}
					}
					else if (left || up) {   //左、上插头存在一个，连通块不变
						int tmp;
						if (left) tmp=left;
						else tmp=up;
						if (a[i][j+1]) {   //插头插向右边的格子
							code[j-1]=0;code[j]=tmp;
							add(p,tot[p^1][k]);
						}
						if (a[i+1][j]) {   //插头插向下边的格子
							code[j-1]=tmp;code[j]=0;
							if (j==m) shift();
							add(p,tot[p^1][k]);
						}
					}
					else {   //左、上插头都不存在。新建连通块
						if (a[i][j+1] && a[i+1][j]) {
							code[j-1]=code[j]=10;   //随意设一个一定不会与之前连通块重复的编号
							add(p,tot[p^1][k]);
						}
					}
				}
			}
		LL ans=0;
		for (int i=1;i<=size[p];i++) ans+=tot[p][i];
		printf("%lld\n",ans);
	}
	return 0;
}