AtCoder Regular Contest 005 C - 器物損壊！高橋君

問題

　の格子状の区画において、各マスは通行可能か不可能かのどちらかとなっている。2回だけ通行不可能なマスを通行できるとき、スタートからゴールまでたどり着けるか判定せよ。

解法

　通行可能ならコスト0、不可能ならコスト1として辺を構築してスタート地点からダイクストラ法を行い、ゴールまでの最短距離が2ならOK。

反省

　一度priority_queueに突っ込む構造体に対する変数の順番を縦と横で逆にしてしまいWA。それ以外は特に詰まることもなかった。

　ダイクストラは流石に書きなれて特に考えることもなくなってきたしなんかライブラリ化したくなってきたが、ノートパソコンだったりデスクトップだったり研究室だったりで複数の環境を使いうるので、共有が面倒くさそうと思ってしまいなかなか。全部Visual Studio使っているしgitとteam servicesで管理してしまえば楽なのかな。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll H, W;
    cin >> H >> W;
    vector<string> c(H);
    for (ll i = 0; i < H; i++) {
        cin >> c[i];
    }

    pair<ll, ll> s, g;
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            if (c[i][j] == 's') {
                s = { i, j };
            } else if (c[i][j] == 'g') {
                g = { i, j };
                c[i][j] = '.';
            }
        }
    }

    vector<vector<ll>> cost(H, vector<ll>(W, INT_MAX));
    struct Element {
        ll cost, x, y;
        bool operator<(const Element& rhs) const {
            return cost > rhs.cost;
        }
    };

    priority_queue<Element> pq;
    cost[s.first][s.second] = 0;
    pq.push({ 0, s.second, s.first });

    auto isOK = [&](ll x, ll y) {
        return (0 <= x && x < W && 0 <= y && y < H);
    };

    ll dx[4] = { 0, 1, 0, -1 };
    ll dy[4] = { 1, 0, -1, 0 };

    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();

        for (ll i = 0; i < 4; i++) {
            ll nx = t.x + dx[i];
            ll ny = t.y + dy[i];
            if (!isOK(nx, ny)) {
                continue;
            }
            ll nc = t.cost + (c[ny][nx] == '.' ? 0 : 1);

            if (nc < cost[ny][nx]) {
                cost[ny][nx] = nc;
                pq.push({ nc, nx, ny });
            }
        }
    }

    cout << (cost[g.first][g.second] <= 2 ? "YES" : "NO") << endl;
}