首页 > 代码库 > CodeForces 676D Theseus and labyrinth
CodeForces 676D Theseus and labyrinth
最短路。
$dis[i][j][k]$记录到点$(i,j)$,门的状态为$k$时的最短路。转移的时候有$8$种方案,即直接走向周围四个点,或者进行旋转。比较烦的是判断两个相邻的点在状态$k$下是否连通,仔细一些就可以了。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-‘0‘; c=getchar();}}const int INF=0x7FFFFFFF;const int maxn=1010;int n,m,sx,sy,ex,ey;char s[maxn][maxn];int dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} };int dis[maxn][maxn][4];bool f[maxn*maxn*4];int tmp[5],tt[5],p1[5],p2[5];struct X{ int st,dis; X(int ST,int DIS){ st=ST; dis=DIS;} bool operator <(const X&a) const { return dis>a.dis; }};bool p(int x,int y){ if(x<0||x>=n) return 0; if(y<0||y>=m) return 0; if(s[x][y]==‘*‘) return 0; return 1;}void get(int a,int b,int st){ memset(tmp,0,sizeof tmp); memset(tt,0,sizeof tt); if(s[a][b]==‘+‘) tmp[0]=1,tmp[1]=1,tmp[2]=1,tmp[3]=1; else if(s[a][b]==‘-‘) tmp[1]=1,tmp[3]=1; else if(s[a][b]==‘|‘) tmp[0]=1,tmp[2]=1; else if(s[a][b]==‘^‘) tmp[0]=1; else if(s[a][b]==‘>‘) tmp[1]=1; else if(s[a][b]==‘v‘) tmp[2]=1; else if(s[a][b]==‘<‘) tmp[3]=1; else if(s[a][b]==‘U‘) tmp[1]=1,tmp[2]=1,tmp[3]=1; else if(s[a][b]==‘R‘) tmp[0]=1,tmp[2]=1,tmp[3]=1; else if(s[a][b]==‘D‘) tmp[0]=1,tmp[1]=1,tmp[3]=1; else if(s[a][b]==‘L‘) tmp[0]=1,tmp[1]=1,tmp[2]=1; for(int i=0;i<4;i++) tt[(i+st)%4]=tmp[i];}bool check(int x1,int y1,int x2,int y2,int st){ get(x1,y1,st); for(int i=0;i<4;i++) p1[i]=tt[i]; get(x2,y2,st); for(int i=0;i<4;i++) p2[i]=tt[i]; if(x1==x2) { if(y1+1==y2) { if(p1[1]==1&&p2[3]==1) return 1; return 0; } else { if(p1[3]==1&&p2[1]==1) return 1; return 0; } } else if(y1==y2) { if(x1+1==x2) { if(p1[2]==1&&p2[0]==1) return 1; return 0; } else { if(p1[0]==1&&p2[2]==1) return 1; return 0; } } return 0;}void spfa(){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) for(int k=0;k<4;k++) dis[i][j][k]=INF; dis[sx][sy][0]=0; priority_queue<X>Q; Q.push(X(sx*m+sy,0)); while(!Q.empty()) { X top=Q.top(); Q.pop(); int st,r,c,h=top.st; st=h/(n*m); h=h-st*(n*m); r=h/m; c=h%m; if(dis[r][c][st]<top.dis) continue; for(int i=0;i<4;i++) { int t=(st+i)%4; if(dis[r][c][st]+i<dis[r][c][t]) { dis[r][c][t]=dis[r][c][st]+i; Q.push(X(r*m+c+t*n*m,dis[r][c][t])); } } for(int i=0;i<4;i++) { int tx=r+dir[i][0],ty=c+dir[i][1]; if(p(tx,ty)==0) continue; if(check(r,c,tx,ty,st)==0) continue; if(dis[r][c][st]+1<dis[tx][ty][st]) { dis[tx][ty][st]=dis[r][c][st]+1; Q.push(X(tx*m+ty+st*n*m,dis[tx][ty][st])); } } }}int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",s[i]); scanf("%d%d",&sx,&sy); sx--; sy--; scanf("%d%d",&ex,&ey); ex--; ey--; spfa(); int ans=INF; for(int i=0;i<4;i++) ans=min(ans,dis[ex][ey][i]); if(ans==INF) printf("-1\n"); else printf("%d\n",ans); return 0;}
CodeForces 676D Theseus and labyrinth
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。