记录编号	597994	评测结果	AAAAAAAAAA
题目名称	插头dp模板（曼哈顿回路	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	0.144 s
提交时间	2024-12-24 21:04:30	内存使用	3.93 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 29987
#define lst now^1
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll n,m,now,endx,endy,ans; 
ll a[15][15],pre[15];
ll hd[30000],nxt[1<<15],dp[2][1<<15],val[2][1<<15],que[2][1<<15],cnt[2];
char c;
void ycl(){
	pre[1]=1;
	for(int i=2;i<=14;i++)pre[i]=pre[i-1]<<2;
}
void insert(ll sta,ll w){
	ll u=sta%mod+1;
	for(int i=hd[u];i;i=nxt[i]){
		if(que[now][i]==sta){
			val[now][i]+=w;
			return;
		}
	}
	nxt[++cnt[now]]=hd[u];
	hd[u]=cnt[now];
	que[now][cnt[now]]=sta;
	val[now][cnt[now]]=w;
}
//void write(ll sta,ll num){
//	for(int i=1;i<=m+1;i++){
//		cout<<sta%4<<" ";
//		sta/=4;
//	}
//	cout<<"val: "<<num;
//	cout<<endl;
//}
void work(){
	val[now][1]=1,que[now][1]=0,cnt[now]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt[lst];j++)que[now][j]=que[now][j]<<2;
		for(int j=1;j<=m;j++){//prej当前格下插头,prej+1当前格右插头 
			memset(nxt,0,sizeof(nxt));
			memset(hd,0,sizeof(hd));
			now=lst;
			cnt[now]=0;
//			cout<<"\n------------------\n";
//			cout<<i<<" "<<j<<endl;
			for(int k=1;k<=cnt[lst];k++){
				ll bit=que[lst][k],num=val[lst][k];
//				write(bit,num);
				ll b1=(bit>>(j-1)*2)%4,b2=(bit>>j*2)%4;//b1左插头,b2上插头 
//				cout<<b1<<" "<<b2<<endl;
				if(!a[i][j]){
					if(!b1&&!b2)insert(bit,num);
				}else{
					if(!b1&&!b2){
						if(a[i][j+1]&&a[i+1][j])insert(bit+pre[j]+pre[j+1]*2,num);
					}else if(!b1){
						if(a[i+1][j])insert(bit-b2*pre[j+1]+pre[j]*b2,num);
						if(a[i][j+1])insert(bit-b2*pre[j+1]+pre[j+1]*b2,num);
					}else if(!b2){
						if(a[i+1][j])insert(bit-b1*pre[j]+pre[j]*b1,num);
						if(a[i][j+1])insert(bit-b1*pre[j]+pre[j+1]*b1,num);
					}else if(b1==1&&b2==1){
						ll p=1;
						for(int bs=j+1;bs<=m;bs++){
							if((bit>>bs*2)%4==1)p++;
							else if((bit>>bs*2)%4==2)p--;
							if(!p){
								insert(bit-b1*pre[j]-b2*pre[j+1]-pre[bs+1],num);
								break;
							}
						}
					}else if(b1==2&&b2==2){
						ll p=1;
						for(int bs=j-2;bs>=1;bs--){
							if((bit>>bs*2)%4==2)p++;
							else if((bit>>bs*2)%4==1)p--;
							if(!p){
								insert(bit-b1*pre[j]-b2*pre[j+1]+pre[bs+1],num);
								break;
							}
						}
					}else if(b1==2&&b2==1){
						insert(bit-b1*pre[j]-b2*pre[j+1],num);
					}else if(i==endx&&j==endy){
						ans+=num;
					}
				}
			}
		}
	}
}
int main(){
	freopen("Manhattan.in","r",stdin);
	freopen("Manhattan.out","w",stdout);
	ycl();
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='.')a[i][j]=1,endx=i,endy=j;
			else a[i][j]=0;
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)cout<<a[i][j]<<" ";
//		cout<<endl;
//	}
	work();
	cout<<ans<<endl;
	return 0;
}