记录编号	490685	评测结果	AAAAAAAAAA
题目名称	[Ural 1519] 一级方程式赛车	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2018-03-11 18:32:00	内存使用	26.25 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Max=300000+10;
const int maxn=20;
int n,m,ex,ey,siz,idx;
int f[2],bit[maxn],head[Max],next[Max],hash[Max],mp[maxn][maxn];
long long sum,dp[2][Max],st[2][Max];
void Hash(long long s,long long num){
	int pos=s%Max;
	for(int i=head[pos];i!=-1;i=next[i]){
		if(st[idx][hash[i]]==s){
			dp[idx][hash[i]]+=num;
			return;
		}
	}
	++f[idx];
	st[idx][f[idx]]=s;
	dp[idx][f[idx]]=num;
	hash[siz]=f[idx],next[siz]=head[pos],head[pos]=siz++;
}
void PlugDP(){
	f[0]=1,dp[0][1]=1;
	for(int i=1;i<=n;i++){
		for(int k=1;k<=f[idx];k++)st[idx][k]<<=2;
		for(int j=1;j<=m;j++){
			memset(head,-1,sizeof(head));
			siz=0,idx^=1,f[idx]=0;
			for(int k=1;k<=f[idx^1];k++){
				long long s=st[idx^1][k],num=dp[idx^1][k];
				int p=(s>>bit[j-1])%4,q=(s>>bit[j])%4;
				if(!mp[i][j]){
					if(!p&&!q)Hash(s,num);}
				else if(!p&&!q){
					if(!mp[i+1][j]||!mp[i][j+1])continue;
					s=s+(1<<bit[j-1])+2*(1<<bit[j]);
					Hash(s,num);
				}
				else if(!p&&q){
					if(mp[i][j+1])Hash(s,num);
					if(mp[i+1][j]){
						s=s+q*(1<<bit[j-1])-q*(1<<bit[j]);
						Hash(s,num);}
				}
				else if(p&&!q){
					if(mp[i+1][j])Hash(s,num);
					if(mp[i][j+1]){
						s=s-p*(1<<bit[j-1])+p*(1<<bit[j]);
						Hash(s,num);}
				}
				else if(p+q==2){
					int b=1;
					for(int h=j+1;h<=m;h++){
						int v=(s>>bit[h])%4;
						if(v==1)b++;
						if(v==2)b--;
						if(!b){
							s=s+(1<<bit[h])-2*(1<<bit[h]);
							break;
						}
					}
					s=s-(1<<bit[j-1])-(1<<bit[j]);
					Hash(s,num);
				}
				else if(p+q==4){
					int b=1;
					for(int h=j-2;h>=0;h--){
						int v=(s>>bit[h])%4;
						if(v==1)b--;
						if(v==2)b++;
						if(!b){
							s=s-(1<<bit[h])+2*(1<<bit[h]);
							break;
						}
					}
					s=s-2*(1<<bit[j-1])-2*(1<<bit[j]);
					Hash(s,num);
				}
				else if(p==1&&q==2){
					if(i==ex&&j==ey)sum+=num;}
				else if(p==2&&q==1){
					s=s-2*(1<<bit[j-1])-(1<<bit[j]);
					Hash(s,num);}
			}
		}
	}
}	
int main(){
	freopen("formula1.in","r",stdin);
	freopen("formula1.out","w",stdout);
	for(int i=0;i<20;i++)bit[i]=i<<1;
	scanf("%d%d",&n,&m);
	char ch;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch;
			mp[i][j]=(ch=='.');
			if(ch=='.')ex=i,ey=j;
		}
	}
	PlugDP();
	printf("%lld\n",sum);
	return 0;
}