记录编号	263670	评测结果	AAAAAAAAAA
题目名称	[Ural 1519] 一级方程式赛车	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-05-25 19:33:57	内存使用	1.46 MiB

/*
Peoblem:Cdq_dp;
Language:c++;
by dydxh;
2016.05.25;
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<ctime>
#include<cstdlib>
#define ll long long
using namespace std;
const int maxn=15;
const int mod=30007;
const int oo=2000000000;
int n,m,ox,oy,now,last,ans;
int maps[maxn][maxn];
int code[maxn];
void Printer(int x){
	for(int i=m;i>=0;i--){
		code[i]=x&3;
		x>>=2;
	}
	for(int i=0;i<=m;i++){
		if(code[i]==0) printf("#");
		else if(code[i]==1) printf("(");
		else printf(")");
	}
	printf("\n");
}
struct Hasher{
	int cnt;
	int head[mod],nex[mod],hash[mod];
	ll val[mod];
	void Initialize(){
		cnt=0;
		memset(head,-1,sizeof(head));
	}
	void insert(int x,ll delta){
		int loc=x%mod;
		for(int i=head[loc];i!=-1;i=nex[i])
			if(hash[i]==x){
				val[i]+=delta;
				return ;
			}
		nex[++cnt]=head[loc],head[loc]=cnt,hash[cnt]=x,val[cnt]=delta;
	}
	void print(){
		printf("cnt=%d\n",cnt);
		for(int i=0;i<mod;i++){
			if(head[i]==-1) continue;
			for(int j=head[i];j!=-1;j=nex[j])
				Printer(hash[j]);
		}
	}
}H[2];
inline int read(){
	int x=0;bool flag=false;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-') flag=true;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
inline int Th(int Status,int th){
	return (Status>>((m-th)<<1))&3;
}
int Lefter(ll Status,int loc){
	int total=0;
	for(int i=loc-1;i>=0;i--){
		int logo=Status>>((m-i)<<1)&3;
		if(logo==1) total++;
		else if(logo==2) total--;
		if(total==1) return i;
	}
}
int Righter(ll Status,int loc){
	int total=0;
	for(int i=loc+1;i<=m;i++){
		int logo=Status>>((m-i)<<1)&3;
		if(logo==1) total++;
		else if(logo==2) total--;
		if(total==-1) return i;
	}
}
void Trans(int x,int y){
	for(int i=1;i<=H[last].cnt;i++){
		int Status=H[last].hash[i],l=Th(Status,y-1),u=Th(Status,y);
		if(maps[x][y]==0){
			Status^=l<<((m-y+1)<<1);
			Status^=u<<((m-y)<<1);
			if(y==m) Status>>=2;
			H[now].insert(Status,H[last].val[i]);
			continue;
		}
		Status^=l<<((m-y+1)<<1);
		Status^=u<<((m-y)<<1);
		if(l==0 && u==0){
			if(maps[x+1][y]==0 || maps[x][y+1]==0) continue;
			Status|=1<<((m-y+1)<<1);
			Status|=2<<((m-y)<<1);
			H[now].insert(Status,H[last].val[i]);
		}
		else if(l==0 || u==0){
			if(maps[x][y+1]!=0){
				Status|=(u+l)<<((m-y)<<1);
				H[now].insert(Status,H[last].val[i]);
				Status^=(u+l)<<((m-y)<<1);
			}
			if(maps[x+1][y]!=0){
				Status|=(u+l)<<((m-y+1)<<1);
				if(y==m) Status>>=2;
				H[now].insert(Status,H[last].val[i]);
			}
		}
		else{
			if(l==1 && u==1){
				int loc=Righter(Status,y);
				Status^=3<<((m-loc)<<1);
				H[now].insert(Status,H[last].val[i]);
			}
			else if(l==1 && u==2){
				if(x!=ox || y!=oy) continue;
				if(y==m) Status>>=2;
				H[now].insert(Status,H[last].val[i]);
			}
			else if(l==2 && u==1)
				H[now].insert(Status,H[last].val[i]);
			else{
				int loc=Lefter(Status,y-1);
				Status^=3<<((m-loc)<<1);
				if(y==m) Status>>=2;
				H[now].insert(Status,H[last].val[i]);
			}
		}
	}
}
void Dynamic(){
	if(ox==0){
		printf("0\n");
		return ;
	}
	now=0,last=1;
	H[0].Initialize(),H[0].insert(0,1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			now^=1,last^=1;
			H[now].Initialize();
			Trans(i,j);
			//printf("i=%d j=%d\n",i,j);
			//H[now].print();
		}
}
int main(){
	freopen("formula1.in","r",stdin);
	freopen("formula1.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			char ch=getchar();
			while(ch!='*' && ch!='.') ch=getchar();
			if(ch=='.') maps[i][j]=1,ox=i,oy=j;
		}
	Dynamic();
	for(int i=1;i<=H[now].cnt;i++)
		ans+=H[now].val[i];
	cout<<ans<<endl;
	return 0;
}