Mujin Programming Challenge 2018 E - 迷路 (500)

E - 迷路

概要

N×Mのマス目が与えられる。マス目は迷路となっており、#が壁を表す。
長さKの文字列dが与えられる。この迷路はこの文字列に従って進むことが出来る。具体的には、文字列はU, D, L, Rの文字から成り、i秒後にi % K + 1文字目の命令に沿って迷路を進む、または進まないことができる。
迷路のSからGに移動するのに必要な時間の最小値を求めよ。

制約

2 ≦ N, M ≦ 1000
1 ≦ K ≦ 10^5

方針

各方向ごとに命令が実行可能な時刻を配列に格納しておく。

探索を行い、迷路の最短脱出時間を調べる。このとき各方向への移動時間は、上記で作成していた実行可能な時間の配列の中から今の時刻以降の最も早い時間を割り出して計算する。最も早い時刻の割り出しには二分探索を使うと高速化できる。

探索を進める順番は時系列順とする。各方向の移動後時刻をPriority Queueに格納し、時刻が早い順に探索してゆく。

解答

Submission #6364631 - Mujin Programming Challenge 2018

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
struct dat{
	ll t, r, c;
};
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N, M, K;
	cin >> N >> M >> K;
 
	string d;
	cin >> d;
 
	vector<string> grid(N);
	rep(i, N) cin >> grid[i];
 
	ll sr, sc, gr, gc;
	rep(i, N) rep(j, M){
		if(grid[i][j] == 'S'){
			sr = i;
			sc = j;
		}else if(grid[i][j] == 'G'){
			gr = i;
			gc = j;
		}
	}
 
	vector<ll> us, ds, ls, rs;
	rep(i, K){
		if(d[i] == 'U'){
			us.push_back(i);
		}else if(d[i] == 'D'){
			ds.push_back(i);
		}else if(d[i] == 'L'){
			ls.push_back(i);
		}else{
			rs.push_back(i);
		}
	}
 
	if(us.size() > 0) us.push_back(us[0] + K);
	if(ds.size() > 0) ds.push_back(ds[0] + K);
	if(ls.size() > 0) ls.push_back(ls[0] + K);
	if(rs.size() > 0) rs.push_back(rs[0] + K);
 
	auto c = [](dat lhs, dat rhs){
		return lhs.t > rhs.t;
	};
 
	ll INF = 1e12;
	vector<vector<ll>> vtime(N, vector<ll>(M, INF));
 
	priority_queue<dat, vector<dat>, decltype(c)> pq(c);
	pq.push((dat){0, sr, sc});
	vtime[sr][sc] = 0;
 
	while(!pq.empty()){
		dat a = pq.top();
		pq.pop();
 
		ll t, r, c;
		t = a.t; r = a.r; c = a.c;
 
		if(r == gr && c == gc){
			cout << t << endl;
			return 0;
		}
 
		if(r > 0 && us.size() > 0 && grid[r-1][c] != '#'){
			ll nt = t + *(lower_bound(us.begin(), us.end(), t % K)) - t % K;
			nt++;
			if(nt < vtime[r-1][c]){
				vtime[r-1][c] = nt;
				pq.push((dat){nt, r-1, c});
			}
		}
 
		if(r < N-1 && ds.size() > 0 && grid[r+1][c] != '#'){
			ll nt = t + *(lower_bound(ds.begin(), ds.end(), t % K)) - t % K;
			nt++;
			if(nt < vtime[r+1][c]){
				vtime[r+1][c] = nt;
				pq.push((dat){nt, r+1, c});
			}
		}
 
		if(c > 0 && ls.size() > 0 && grid[r][c-1] != '#'){
			ll nt = t + *(lower_bound(ls.begin(), ls.end(), t % K)) - t % K;
			nt++;
			if(nt < vtime[r][c-1]){
				vtime[r][c-1] = nt;
				pq.push((dat){nt, r, c-1});
			}
		}
 
		if(c < M-1 && rs.size() > 0 && grid[r][c+1] != '#'){
			ll nt = t + *(lower_bound(rs.begin(), rs.end(), t % K)) - t % K;
			nt++;
			if(nt < vtime[r][c+1]){
				vtime[r][c+1] = nt;
				pq.push((dat){nt, r, c+1});
			}
		}
	}
 
	cout << -1 << endl;
}