Mujin Programming Challenge 2018 E - 迷路

E - 迷路

問題概要

N行M列 ($ N, M \leq 1000$) のグリッド上をロボットがSからGまで移動するのに最短何秒かかるか求める． ただし，1マス上下左右に動くのにかかる時間は1秒で，毎秒動ける方向が決まっている．動ける方向は長さk ($ k \leq 100000$) の文字列dによって与えられる．いま，ロボットが動き出してからt秒後とすると，ロボットが動ける方向はdのt%k文字目 (0-indexed) で表される．

解法概要

「ロボットが動き出してからt秒のとき，次にロボットが1マス上 (下・左・右) に動けるのは何秒後か」をあらかじめ計算しておくことで，ダイクストラ法によって最短時間を求めることができる．ロボットの動ける方向はk秒周期で決まるので0秒目からk-1秒目までの「次にロボットが1マス上 (下・左・右) に動けるのは何秒後か」を保持しておけばよく，事前計算の最悪時間計算量は$ O \left( k \right)$ ．ただし，d = UDRRLでt=4のときの "次に上に動ける時間" など，次に指定の方向に動くまでに t%k = 0 をまたぐ場合があるので，プログラムでは2k秒ぶんのループを回している．

この事前計算の結果をグラフの辺のコストとし，上下左右に隣接しているマス同士にエッジが張られていると考え，ダイクストラ法を適用する．ダイクストラ法の最悪時間計算量は$ O \left( \left(V+E\right) \log V \right)$ (V,Eはそれぞれ頂点，辺の数) なので，制限時間の2秒には間に合う．

ソースコード

#include <iostream>
#include <queue>
#include <string>
#include <utility>

using namespace std;

typedef pair<int, int> Pii;
typedef long long ll;

const int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};
const char dyx_chars[4] = {'R', 'U', 'L', 'D'};
const ll INF = (1LL << 60);

int n,m,k;
string s[1001],d;
ll shortest[1001][1001], times[100000][4];

struct State {
    ll t, y, x;
    State(ll t, int y, int x): t(t), y(y), x(x) {}
    bool operator>(const State& s) const{
        return t > s.t;
    }
};

void calc_times() {
    fill(times[0], times[k-1]+4, -1);
    for(int j=0;j<4;++j) {
        if(d[k-1] == dyx_chars[j]) times[k-1][j] = 1;
    }
    for(int i=2*k-2;i>=0;--i) {
        for(int j=0;j<4;++j) {
            if(d[i%k] == dyx_chars[j]) {
                times[i%k][j] = 1;
            } else {
                if(times[(i+1)%k][j] == -1) {
                    times[i%k][j] = -1;
                } else {
                    times[i%k][j] = times[(i+1)%k][j] + 1;
                }
            }
        }
    }
}

void dijkstra(Pii start) {
    priority_queue<State, vector<State>, greater<State> > que;
    que.push(State(0LL, start.first, start.second));
    while(!que.empty()) {
        State st = que.top(); que.pop();
        if(shortest[st.y][st.x] < st.t) continue;
        for(int i=0;i<4;++i) {
            int yy = st.y + dyx[i][0], xx = st.x + dyx[i][1];
            if(yy < 0 || n <= yy || xx < 0 || m <= xx || s[yy][xx] == '#' || times[st.t%k][i] == -1) continue;
            if(shortest[yy][xx] > shortest[st.y][st.x] + times[st.t%k][i]) {
                shortest[yy][xx] = shortest[st.y][st.x] + times[st.t%k][i];
                que.push(State(shortest[yy][xx], yy, xx));
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    cin >> d;
    Pii start, goal;
    fill(shortest[0], shortest[n-1]+m, INF);
    for(int i=0;i<n;++i) {
        cin >> s[i];
        for(int j=0;j<m;++j) {
            if(s[i][j] == 'S') {
                start = Pii(i,j);
                shortest[i][j] = 0;
            } else if(s[i][j] == 'G') {
                goal = Pii(i, j);
            }
        }
    }

    calc_times();
    dijkstra(start);

    cout << (shortest[goal.first][goal.second] == INF ? -1 : shortest[goal.first][goal.second]) << endl;
}

所感

本番ではDで詰まっていてEは見ることもしなかったけど，これは明らかにEの方が得意なタイプだったので見るべきだった．