Submission #2996505

---

Source Code Expand

#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.first, s.second });

    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, ny, nx });
            }
        }
    }

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

Submission Info

Judge Result