kmjp's blog

競技プログラミング参加記です

Mujin Programming Challenge 2018 : E - 迷路

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

まとめ

まぁこれはすんなり。