记录编号	384117	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Ural 1519] 一级方程式赛车	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.481 s
提交时间	2017-03-17 13:41:34	内存使用	12.41 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
char s[13][13];
int n,m,q[N],size,d[N][13];
ll dp[2][N];
void set(int &x,int p,int tp){
	x&=~(3<<(p<<1));
	x|=(tp<<(p<<1));
}
int get(int x,int p){return (x>>(p<<1))&3;}
int stack[N],top;
struct hash_table{
	int key[N],val[N];
	hash_table(){memset(key,-1,sizeof key);}
	int operator [] (const int x){
		int ans=0;
		for (int i=x;i;i/=13) ans=(ans*23+i%13)%N;
		while (key[ans]!=-1&&key[ans]!=x) ans==N-1?ans=0:ans++;
		if (key[ans]==-1){
			top=0;
			for (int i=0;i<=m;i++){
				int tp=get(x,i);
				if (tp==1) stack[++top]=i;
				if (tp==2){
					d[size][i]=stack[top];
					d[size][stack[top--]]=i;
				}
			}
			val[ans]=size;
			q[size++]=x;
			key[ans]=x;
		}
		return val[ans];
	}
}tag;
int main()
{
	freopen("formula1.in","r",stdin);
	freopen("formula1.out","w",stdout);
	scanf("%d%d",&n,&m);
	int pos=0;
	for (int i=0;i<n;i++){
		scanf("%s",s[i]);
		for (int j=0;j<m;j++) pos+=(s[i][j]=='.');
	}
	ll *x=dp[0],*y=dp[1],ans=0;
	x[tag[0]]=1;
	for (int i=0;i<n;i++,swap(x,y)){
		for (int j=0;j<m;j++,swap(x,y))
		if (s[i][j]=='.'){
			pos--;
			for (int k=0;k<size;k++) y[k]=0;
			for (int k=0;k<size;k++)
			if (x[k]){
				int S=q[k],right=get(S,j),down=get(S,j+1);
				if (right==1&&down==2){
					set(S,j,0);set(S,j+1,0);
					if (!S&&!pos) ans=x[k];
				}
				else
				if (!right&&!down){
					set(S,j,1);set(S,j+1,2);
					y[tag[S]]+=x[k];
				}
				else
				if ((!right)^(!down)){
					int p=right|down;
					set(S,j,p);set(S,j+1,0);y[tag[S]]+=x[k];
					set(S,j,0);set(S,j+1,p);y[tag[S]]+=x[k];
				}
				else{
					int l=d[k][j],r=d[k][j+1];
					if (l>r) swap(l,r);
					set(S,l,1);set(S,r,2);
					set(S,j,0);set(S,j+1,0);
					y[tag[S]]+=x[k];
				}
			}
		}
		else{
			for (int k=0;k<size;k++) y[k]=0;
			for (int k=0;k<size;k++)
			if (x[k]){
				int S=q[k];
				if (!get(S,j)&&!get(S,j+1)) y[k]+=x[k];
			}
		}
		for (int k=0;k<size;k++) y[k]=0;
		for (int k=0;k<size;k++)
		if (x[k]){
			int S=q[k];
			if (!get(S,m)) y[tag[S<<2]]+=x[k];
		}
	}
	printf("%lld\n",ans);
	return 0;
}