记录编号	573031	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Ural 1519] 一级方程式赛车	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.410 s
提交时间	2022-07-14 21:01:45	内存使用	1.85 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N=12+3;
const int M=40001;
int n,m,endx,endy,now=0; 
int mp[N][N]={0};
int tot[3];
int que[3][M]={0};
ll dp[3][M]={0},ans=0;
int fst[N]={0};
map<int,int>hsh[3];
map<int,int>::iterator qaz;
void hs(int s,ll t){
	qaz=hsh[now].find(s);
	if (qaz!=hsh[now].end()){
		dp[now][qaz->second]+=t;
		return ;
	}
	tot[now]++;
	dp[now][tot[now]]=t;
	que[now][tot[now]]=s;
	hsh[now][s]=tot[now];
	return ;
}
void solve(){
	tot[0]=1;
	dp[0][1]=1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=tot[now];j++){
			hsh[now][que[now][j]]=0;
			que[now][j]>>=2;
			hsh[now][que[now][j]]=j;
		}
		for (int j=1;j<=m;j++){
			now^=1;
			tot[now]=0; hsh[now].clear();
			for (int k=1;k<=tot[now^1];k++){
				int s=que[now^1][k];
				ll t=dp[now^1][k];
				int p=(s>>fst[m+1-j])%4,q=(s>>fst[m-j])%4;
				if (mp[i][j]!=0&&p==0&&q==0){
					hs(s,t);
					continue;
				}
				if (p==0&&q==0){
					if (mp[i][j+1]!=0||mp[i+1][j]!=0)continue;
					hs(s+(1<<fst[m+1-j])+2*(1<<fst[m-j]),t);
					continue;
				}
				if (p==1&&q==1){
					int wxc=1;
					for (int l=m-j-1;l>=0;l--){
						int fjl=(s>>fst[l])%4;
						if (fjl==1)wxc++;
						if (fjl==2)wxc--;
						if (wxc==0){
							hs(s-(1<<fst[m+1-j])-(1<<fst[m-j])-(1<<fst[l]),t);
							break;
						}
					} 
					continue;
				}
				if (p==2&&q==2){
					int wxc=1;
					for (int l=m+1-j+1;l<=m+1;l++){
						int fjl=(s>>fst[l])%4;
						if (fjl==1)wxc--;
						if (fjl==2)wxc++;
						if (wxc==0){
							hs(s-2*(1<<fst[m+1-j])-2*(1<<fst[m-j])+(1<<fst[l]),t);
							break;
						}
					} 
					continue;
				}
				if (p==1&&q==2){
					if (i==endx&&j==endy){
						ans+=t;
					}
					continue;
				}
				if (p==2&&q==1){
					hs(s-2*(1<<fst[m+1-j])-(1<<fst[m-j]),t);
					continue;
				}
				if (p==0&&q!=0){
					if (mp[i+1][j]==0)hs(s+q*(1<<fst[m+1-j])-q*(1<<fst[m-j]),t);
					if (mp[i][j+1]==0)hs(s,t);
					continue;
				}
				if (p!=0&&q==0){
					if (mp[i+1][j]==0)hs(s,t);
					if (mp[i][j+1]==0)hs(s+p*(1<<fst[m-j])-p*(1<<fst[m+1-j]),t);
					continue;
				}
			}
		}
	}
}
int main(){
	freopen ("formula1.in","r",stdin);
	freopen ("formula1.out","w",stdout);
	memset(mp,-1,sizeof(mp));
	scanf("%d%d",&n,&m);
	for (int i=0;i<=13;i++)fst[i]=i<<1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			char t;
			cin>>t;
			if (t=='.'){
				endx=i,endy=j;
				mp[i][j]=0;
			}
		}
	}
	solve();
	printf("%lld\n",ans);
	return 0;
}