はまやんはまやんはまやん

hamayanhamayan's blog

こたつがめを燃やさないで [Ritsumeikan University Competitive Programming Camp 2019 Day 2 E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/E

前提知識

解説

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419049

ダイクストラで解く。
dis[y][x] := (x,y)へ到達するための最小コスト
ダイクストラをしていくのだが、

  • 上下左右にコストAで移動する
  • コストBで能力を使い、周囲8方向にコストAで移動する

で移動を行う。
能力で消えた塀を状態に含める必要は無い。
もし、後々消えた塀の所を移動する事になった場合は、
それよりも前に移動すべきであり、周り道をする必要は無いからである。

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int H, W, A, B;
string C[1010];
int vis[1010][1010]; ll dis[1010][1010];
min_priority_queue<pair<ll, int>> que;
enum { UP = 0, UP_RIGHT, RIGHT, DOWN_RIGHT, DOWN, DOWN_LEFT, LEFT, UP_LEFT };
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> A >> B;
    rep(y, 0, H) cin >> C[y];

    rep(y, 0, H) rep(x, 0, W) dis[y][x] = infl;

    int sx, sy;
    rep(y, 0, H) rep(x, 0, W) if (C[y][x] == 's') {
        sx = x;
        sy = y;
    }

    dis[sy][sx] = 0;
    que.push({ 0, sy * 1010 + sx });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll c = q.first;
        int x = q.second % 1010;
        int y = q.second / 1010;

        if (C[y][x] == 'g') {
            cout << dis[y][x] << endl;
            return;
        }

        if (vis[y][x]) continue;
        vis[y][x] = 1;

        rep(i, 0, 8) if ((i & 1) == 0) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue;
            if (C[yy][xx] == '#') continue;
            if (chmin(dis[yy][xx], c + A)) que.push({ dis[yy][xx], yy * 1010 + xx });
        }

        int ok = 1;
        if (C[y][x] == '*') ok = 0;
        rep(i, 0, 8) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue;
            if (C[yy][xx] == '*') ok = 0;
        }

        if (ok) {
            rep(i, 0, 8) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue;
                int d = abs(x - xx) + abs(y - yy);
                if (chmin(dis[yy][xx], c + B + A * d)) que.push({ dis[yy][xx], yy * 1010 + xx });
            }
        }
    }

    cout << "INF" << endl;
}