9.18考试 第三题chess题解
2024-08-31 21:29:47
在讲这道题之前我们先明确一个丝薄出题人根本没有半点提示却坑死了无数人的注意点:
走敌人和不走敌人直接到时两种走法,但只走一个敌人和走一大坨敌人到同一个点只算一种方案(当然,前提是步骤一致)。
当时看完所有题后打算第一个打这道题,当时第一反应以为只是一个普普通通的宽搜,然后就发现我需要记录一下他走过那些敌人,然后就开始懵逼了,dfs能记录但太慢,bfs较快但无法记录,然后我只能在bfs中传递结构体,里面包含一个vector然后就全E了……
其实当时自己也是犯浑,过于局限于传统的棋盘搜索题了,对于敌人我们可以通过缩边,将敌人两侧的空格连在一起,然后就不必去担心卡死在里面了。不过我的方法相当麻烦,首先先对大棋盘建边,然后挨个tarjan,缩可以相互到达的敌人,然后又得重新建边,然后又需要在新边的基础上去缩边,总共搞了3次,自己都烦了,只能说挺练代码能力的……真的挺练的……
当然,我们完全可以dfs一下所有的敌人然后对于所有他们能连到的点之间相互建边,结果本博主太懒了,然后打了一个长了不知道几百倍的代码……
然后就是比较简单的spfa了。
不过对于第二问的答案,既然人家说了是long long 级别的,就一定有他的道理(虽然刚刚经过本博主踩雷发现改为int完全没问题,丝薄出题人……),所以由于棋盘有一个特殊性质:距离短的一定搜的早,所以我们只用记录一下到该点的方案数,更新距离是直接转移就好了。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<cmath> #include<map> #include<vector> #define N 53 using namespace std; int n,m,c[N][N],zz1,zz2,zz5,zz,b[N*N],d[N*N],a[N*N]; ][]; int bh[N][N]; struct ro{ int to,l; int next; }road[N*N*],road2[N*N*],road3[N*N*]; void build2(int x,int y,int z) { zz2++; road2[zz2].to=y; road2[zz2].next=b[x]; road2[zz2].l=z; b[x]=zz2; } void build3(int x,int y,int z) { zz5++; road3[zz5].to=y; road3[zz5].l=z; road3[zz5].next=d[x]; d[x]=zz5; } void build(int x,int y) { zz++; road[zz].to=y; road[zz].next=a[x]; a[x]=zz; road[zz].l=; } bool check(int x,int y) { ||x>n); ||y>m); ); ; } bool rz[N*N],rz2[N*N],lt[N*N][N*N],lt2[N*N][N*N],rd[N*N]; ],top,dfn[N*N],low[N*N],zz3,belong[N*N],zz4,c2[N*N]; void tar(int x) { zz3++; low[x]=dfn[x]=zz3; rz[x]=rz2[x]=; top++; st[top]=x; ;i=road2[i].next) { int y=road2[i].to; ||c2[x]!=)continue; if(!rz2[y]) { tar(y); low[x]=min(low[x],low[y]); } else if(rz[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]) { int v; zz4++; do{ v=st[top]; belong[v]=zz4; top--; rz[v]=; }while(dfn[v]!=low[v]); } } int dis[N*N],sx,sy,tx,ty,js[N*N]; void spfa() { memset(dis,0xf,sizeof(dis)); rd[belong[bh[sx][sy]]]=; dis[belong[bh[sx][sy]]]=; queue<int> q1; q1.push(belong[bh[sx][sy]]); js[belong[bh[sx][sy]]]=; while(!q1.empty()) { int x=q1.front();q1.pop(); rd[x]=; if(x==belong[bh[tx][ty]])continue; ;i=road[i].next) { int y=road[i].to; if(dis[y]>dis[x]+road[i].l) { dis[y]=dis[x]+road[i].l; js[y]=; js[y]+=js[x]; if(!rd[y]) { q1.push(y); rd[y]=; } } else if(dis[y]==dis[x]+road[i].l) js[y]+=js[x]; } } } int main() { scanf("%d%d",&n,&m); ;i<=n;i++) { ;j<=m;j++) { zz1++; bh[i][j]=zz1; scanf("%d",&c[i][j]); c2[zz1]=c[i][j]; ) sx=i,sy=j; ) tx=i,ty=j; } } zy[][]=-,zy[][]=-; zy[][]=,zy[][]=-; zy[][]=,zy[][]=; zy[][]=-,zy[][]=; zy[][]=-,zy[][]=-; zy[][]=,zy[][]=-; zy[][]=-,zy[][]=; zy[][]=,zy[][]=; ;i<=n;i++) { ;j<=m;j++) { ;k<=;k++) { )continue; ],ty=j+zy[k][]; if(!check(tx,ty))continue; ; )cj=; build2(bh[i][j],bh[tx][ty],cj); } } } ;i<=n;i++) { ;j<=m;j++) { )continue; if(!rz2[bh[i][j]]) tar(bh[i][j]); } } ;i<=n;i++) { ;j<=m;j++) { )continue; int t=bh[i][j]; ;k=road2[k].next) { int y=belong[road2[k].to]; if(y!=belong[t]&&!lt[belong[t]][y]) { lt[belong[t]][y]=; build3(belong[t],y,road2[k].l); } } } } memset(lt,,sizeof(lt)); ;i<=zz4;i++) { ;j=road3[j].next) { int y=road3[j].to; ) { ;k=road3[k].next) { int z=road3[k].to; if(z!=i&&!lt2[i][z]) build(i,z),lt2[i][z]=; } } else if(!lt[i][y]) build(i,y),lt[i][y]=; } } spfa(); ]) printf("-1\n"); else printf(,js[belong[bh[tx][ty]]]); ; }
最新文章
- Mysql 分区
- nginx lua整合安装
- linux下报错处理经验
- Hdu 4738【求无向图的桥】.cpp
- ASP.NET Web API的消息处理管道: Self Host下的消息处理管道[上篇]
- JS网站当前日期在IE9、Chrome和FireFox中年份显示为113年的解决方法 getFullYear();
- Oak Seeds 网站项目回顾
- Gym - 101102C线段树
- java泛型(整理)
- C#用panel实现子窗体的切换
- SubTool 电影字幕下载程序
- 代码审计之XiaoCms(后台任意文件上传至getshell,任意目录删除,会话固定漏洞)
- ACM Meteor Shower
- Unity切换到安卓平台Shader丢失(opengl)
- MTV 和 MVC
- 3、SourceTree通过PUTTY连接GitLab
- Golang 调用 Python 代码
- netty源码解解析(4.0)-3 Channel的抽象实现
- webstom 快捷键
- thymeleaf 字面量