迷路 [Mujin Programming Challenge 2018 E]

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e

前提知識

• ダイクストラ

考察過程

1. ダイクストラの問題に見える
2. 状態を考えるとマスの数NMで時間がKなのでNMK=10^11なのでこれは無理
3. なんとか改善できないか
4. 最短時間から、4方向へ移動するためのコストが計算できる（どれくらい待てばいいか分かる）
5. 時間Kは持たなくていい？
6. O(NM)でダイクストラならいける

解説

https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2947402

ダイクストラしよう。
全てのマスを状態として持ってダイクストラする。
移動コストは時間によってはその方向に移動するために待つ必要があるので、
その時間を足したものが移動コストになる。
　
移動コストの計算のために、移動のための待ち時間を事前計算しておこう。
make_wait関数を使って、以下の配列を用意する。
wait[k][d] := 時間%K=kの時にd方向へ移動するのに必要な待ち時間
プログラムが何をしているかわかりにくいと思うが、
① 全てinfにしておく
② 方向dへ即座に移動できる場合を先に確定する（=0で）
③ ②で確定した所から時間をさかのぼって、まだ未確定になっている所の時間を更新する
という感じで作る。
　
あとは、一般的なダイクストラを書く。
コスト部分だけc + wait[c%K][d] + 1のようになる。
c：今までのコスト
wait[c%K][d]：必要待ち時間
1：移動するのに1秒かかる

int H, W, K; string D, S[1010];
ll wait[101010][4];
//---------------------------------------------------------------------------------------------------
map<char, int> dir = { { 'U', 0 },{ 'R', 1 },{ 'D', 2 },{ 'L', 3 } };
enum { UP = 0, RIGHT, DOWN, LEFT };
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//---------------------------------------------------------------------------------------------------
void make_wait() {
    rep(k, 0, K) rep(d, 0, 4) wait[k][d] = infl;
 
    rep(k, 0, K) wait[k][dir[D[k]]] = 0;
    rep(k, 0, K) {
        int d = dir[D[k]];
        int i = (k - 1 + K) % K;
        ll c = 1;
        while (wait[i][d] == infl) {
            wait[i][d] = c;
            c++;
            i = (i - 1 + K) % K;
        }
    }
}
//---------------------------------------------------------------------------------------------------
ll dp[1010][1010]; int vis[1010][1010];
ll dijk(int sx, int sy) {
    min_priority_queue<pair<ll, int>> que;
 
    rep(y, 0, H) rep(x, 0, W) dp[y][x] = infl;
    rep(y, 0, H) rep(x, 0, W) vis[y][x] = 0;
 
    dp[sy][sx] = 0;
    que.push({ 0, sy * 1010 + sx });
 
    while (!que.empty()) {
        auto q = que.top();
        que.pop();
 
        int x = q.second % 1010;
        int y = q.second / 1010;
        ll c = q.first;
 
        if (vis[y][x]) continue;
        vis[y][x] = 1;
        
        if (S[y][x] == 'G') return c;
 
        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                if (S[yy][xx] != '#') {
                    ll cc = c + wait[c%K][d] + 1;
                    if (cc < dp[yy][xx]) {
                        dp[yy][xx] = cc;
                        que.push({ cc, yy * 1010 + xx });
                    }
                }
            }
        }
    }
 
    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K >> D;
    rep(y, 0, H) cin >> S[y];
 
    make_wait();
    
    int sx, sy;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == 'S') sx = x, sy = y;
    ll ans = dijk(sx, sy);
    printf("%lld\n", ans);
}