比赛 |
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;
}