比赛 SBOI虎年首秀 评测结果 AAAAAAAAAAATATAAAAAA
题目名称 一级方程式赛车 最终得分 90
用户昵称 op_组撒头屯 运行时间 2.811 s
代码语言 C++ 内存使用 2.84 MiB
提交时间 2022-02-23 19:10:47
显示代码纯文本
#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};
void hs(int s,ll t){
	for (int i=1;i<=tot[now];i++){
		if (que[now][i]==s){
			dp[now][i]+=t;
			return ;
		}
	}
	tot[now]++;
	dp[now][tot[now]]=t;
	que[now][tot[now]]=s;
	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++)que[now][j]>>=2;
		for (int j=1;j<=m;j++){
			now^=1;
			tot[now]=0; 
			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;
}