| 记录编号 |
548042 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[Ural 1519] 一级方程式赛车 |
最终得分 |
100 |
| 用户昵称 |
 瑆の時間~無盡輪迴·林蔭 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.295 s |
| 提交时间 |
2019-12-31 12:36:18 |
内存使用 |
20.95 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int head[300001],nxt[2<<16],que[2][2<<16],val[2][2<<16],cnt[2],inc[15];
const int maxn=15;
const int HS=299987;
int n,m,ex,ey,now,last,ans;
int map[maxn][maxn];
char S;
void init()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>S;
if(S=='.')
{
map[i][j]=1;
ex=i,ey=j;
}
}
}
inc[0]=1;
for(int i=1;i<=12;i++)
{
inc[i]=inc[i-1]*4;
}
}
void INSERT(int ids,int num)
{
int U=ids%HS+1;//保证状态哈希值不为0
for(int i=head[U];i;i=nxt[i])
{
if(que[now][i]==ids)
{
//是这种状态
val[now][i]+=num;
return;
}
}
//没有出现过
cnt[now]++;
nxt[cnt[now]]=head[U];
head[U]=cnt[now];
que[now][cnt[now]]=ids;
val[now][cnt[now]]=num;
}
void WORK()
{
//对于一个格子J，从J向下的插头的贡献是inc[j-1],向右的贡献是inc[j]
cnt[now]=1;
que[now][1]=0;//不向下一行遗传一个插头的初始状态
val[now][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=cnt[now];j++)
que[now][j]<<=2;//全部删去来自上一行末尾的右插头，并给这一行第一个加上一个虚拟插头(不存在)
//因为这项操作是一行进行一次，所以可以保证，被删去的一定是来自上一行末尾的右插头
for(int j=1;j<=m;j++)
{
last=now;
now^=1;
memset(head,0,sizeof(head));
cnt[now]=0;
for(int k=1;k<=cnt[last];k++)
{
int bit=que[last][k],num=val[last][k];
int b1=(bit>>((j-1)*2))%4;//J格的右插头存在于J-1的位置；
int b2=(bit>>(j*2))%4;//J格子的下插头存在于J位置；
if(!map[i][j])
{
if(!b1&&!b2)
{
//障碍点且没有点需要用插头通过它进行联通
INSERT(bit,num);
}
//否则一定不合法
}
else
{
if(!b1&&!b2)
{
//如果这个点必须要走且目前在轮廓线上方不与任何点相连
//那么必须要和下方点和右方点均相连
if(map[i][j+1]&&map[i+1][j])
INSERT(bit+inc[j-1]+2*inc[j],num);
//下方点位置是j-1，右方点是j
//因为转移过后已经开始对格子J+1进行操作了。
//此时状态代表的是J+1
}
else
{
if(!b1&&b2)
{
//有一个从上面插到这个点的插头
//可以选择向右出去或者向下出去，只能选一个
//但是不管怎样，插头的括号性质不变
if(map[i][j+1])
INSERT(bit-inc[j]*b2+inc[j]*b2,num);//先减去上面插头的贡献，再算上向右的插头的贡献
if(map[i+1][j])
INSERT(bit-inc[j]*b2+inc[j-1]*b2,num);//先消去上面插头的贡献，再算向下插头的贡献
}
else
{
if(b1&&!b2)
{
//大体同上，有一个从左面插到这个点的插头(这个点的右插头)
//也是可以选择向右或者向下
//插头性质仍然不变
if(map[i+1][j])
{
INSERT(bit-inc[j-1]*b1+inc[j-1]*b1,num);//先减去右插头的贡献，然后对下面状态后推
}
if(map[i][j+1])
INSERT(bit-inc[j-1]*b1+inc[j]*b1,num);
}
else
{
if(b1==1&&b2==1)
{
int kel=1;
//两者都是左括号，但是能配对，消去贡献，但是要对j+1即以后的节点进行检查，把第一个找到的多出来的右括号改成左括号
for(int l=j+1;l<=m;l++)
{
int seds=(bit>>(l*2))%4;
if(seds==1)
kel++;
if(seds==2)
kel--;
if(kel==0)
{
INSERT(bit-inc[j-1]-inc[j]-inc[l],num);//将两个配对的括号消去，并且将找到的第一个多出来的右括号改成左括号
break;//改完就走
}
}
}
else
{
if(b1==2&&b2==2)
{
int kel=1;
//几乎同上，只不过把寻找多出来的右括号换成寻找左括号，然后从j-2找到1
for(int l=j-2;l>=0;l--)
{
int seds=(bit>>(l*2))%4;
if(seds==1)
kel--;
if(seds==2)
kel++;
if(kel==0)
{
INSERT(bit-inc[j-1]*2-inc[j]*2+inc[l],num);//将两个配对的括号消去，并且将找到的第一个多出来的左括号改成右括号
break;//改完就走
}
}
}
else
{
if(b1==2&&b2==1)
{
//直接连接起来就好
INSERT(bit-inc[j-1]*2-inc[j],num);
}
else
{
if(ex==i&&ey==j)
{
//这时就已经只剩下b1==1,b2==2了
//也就是此时一定行成了一个闭环，如果不是终点那一定不对
ans+=num;
}
}
}
}
}
}
}
}
}
}
}
}
signed main()
{
freopen("formula1.in","r",stdin);
freopen("formula1.out","w",stdout);
init();
WORK();
printf("%lld",ans);
return 0;
}