けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

MUJIN 2018 E - 迷路 (500 点)

各地点に早くたどり着いておくに越したこと無い系問題!!

atcoder.jp

問題概要

 N × M のグリッドがあってスタートからゴールへと行きたい。壁のあるマスは通れない。

ただし毎秒ごとに移動できる方向に制限がある。 K で割ったあまりがそれぞれの場合についてどの方向に移動できるかがあたえられる。最短路長を求めよ。

制約

  •  2 \le N, M \le 1000
  •  1 \le K \le 10^{5}

考えたこと

今なら典型に思える。
いわゆる「刻一刻と盤面の状態が時間変化する」というタイプの問題であるが、そのタイプの問題では

  • とにかく各地点に早く到達して問題無い
  • 到達後どのタイミングで次の手を打つかは到達時点で待機すればよい

という構造を利用することがほとんどな気がする。さてそれがわかれば簡単で

  • ノード v にいるとき四方向のノードへの更新 (緩和) は
    • 壁があったら更新しない
    • 壁がなかったら、dp[ v ] の時点から見て、その方向へ移動できる最速のタイミングで移動する

とすればよい。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;
const long long INF = 1LL<<60;
const int dx[4] = {1, 0, -1, 0}; // D, R, U, L
const int dy[4] = {0, 1, 0, -1};
bool chmin(long long &a, long long b) {if (a > b) {a = b; return true;} return false;}

int N, M, K;
string d;
vector<string> fi;

int main() {
    cin >> N >> M >> K >> d;
    fi.resize(N);
    int sx, sy, tx, ty;
    for (int i = 0; i < N; ++i) {
        cin >> fi[i];
        for (int j = 0; j < M; ++j) {
            if (fi[i][j] == 'S') sx = i, sy = j;
            else if (fi[i][j] == 'G') tx = i, ty = j;
        }
    }
    vector<long long> timing[4];
    for (int i = 0; i < K; ++i) {
        int dir = -1;
        if (d[i] == 'D') dir = 0;
        else if (d[i] == 'R') dir = 1;
        else if (d[i] == 'U') dir = 2;
        else dir = 3;
        timing[dir].push_back(i); timing[dir].push_back(i+K);
    }
    for (int dir = 0; dir < 4; ++dir) sort(timing[dir].begin(), timing[dir].end());

    vector<vector<long long> > dp(N, vector<long long>(M, INF));
    dp[sx][sy] = 0;
    priority_queue<pair<long long,pint>, vector<pair<long long,pint> >,
                   greater<pair<long long,pint> > > que;
    que.push({0, pint(sx, sy)});
    while (!que.empty()) {
        auto cur = que.top(); que.pop();
        long long dist = cur.first;
        int x = cur.second.first;
        int y = cur.second.second;
        if (dist > dp[x][y]) continue;
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M || timing[dir].empty()) continue;
            if (fi[nx][ny] == '#') continue;
            int ord = dist % K;
            auto it = lower_bound(timing[dir].begin(), timing[dir].end(), ord);
            long long wait = *it - ord;
            long long ndist = dist + wait + 1;
            if (chmin(dp[nx][ny], ndist)) {
                que.push({ndist, pint(nx, ny)});
            }
        }
    }
    cout << (dp[tx][ty] < INF ? dp[tx][ty] : -1)  << endl;
}