Fまでは割と順調に解けたので良かったね。
https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e
問題
移動不可なマスを含む2次元グリッド上で、スタートからゴールまで隣接セルを辿って移動する最短時刻を求めよ。
なお、各時刻において上下左右移動可能な向きは固定されており、その周期はKである。
解法
前処理として、各時刻について、次に上下左右に移動できる最初のタイミングを求めておく。
そうするとあとは単なるダイクストラの要領で解くことができる。
int H,W,K; string T; string S[1010]; ll nex[201010][4]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; ll D[2020][2020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>K; cin>>T; T+=T; FOR(i,4) nex[2*K][i]=1LL<<40; for(i=2*K-1;i>=0;i--) { FOR(j,4) nex[i][j]=nex[i+1][j]; if(T[i]=='U') nex[i][3]=i; if(T[i]=='D') nex[i][1]=i; if(T[i]=='L') nex[i][2]=i; if(T[i]=='R') nex[i][0]=i; } int SX,SY,GY,GX; FOR(y,H) { cin>>S[y]; FOR(x,W) { if(S[y][x]=='S') SX=x,SY=y; if(S[y][x]=='G') GX=x,GY=y; } } FOR(y,H) FOR(x,W) D[y][x]=1LL<<50; priority_queue<pair<ll,int>> Q; D[SY][SX]=0; Q.push({0,SY*10000+SX}); while(Q.size()) { ll co=-Q.top().first; if(co>=1LL<<50) break; int cy=Q.top().second/10000; int cx=Q.top().second%10000; Q.pop(); if(D[cy][cx]!=co) continue; int id=co%K; FOR(i,4) if(nex[id][i]<1LL<<40) { int ty=cy+dy[i]; int tx=cx+dx[i]; if(ty<0 || ty>=H || tx<0 || tx>=W || S[ty][tx]=='#') continue; ll nc=co+(nex[id][i]-id)+1; if(D[ty][tx]>nc) { D[ty][tx]=nc; Q.push({-nc,ty*10000+tx}); } } } ll ret=D[GY][GX]; if(ret>=1LL<<50) ret=-1; cout<<ret<<endl; }
まとめ
まぁこれはすんなり。