Submission #2996539


Source Code Expand

Copy
#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;
}

Submission Info

Submission Time
Task C - 器物損壊!高橋君
User tokumini
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1538 Byte
Status
Exec Time 38 ms
Memory 7032 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt 1 ms 256 KB
00_min_02.txt 1 ms 256 KB
00_min_03.txt 1 ms 256 KB
00_min_04.txt 1 ms 256 KB
00_min_05.txt 1 ms 256 KB
00_min_06.txt 1 ms 256 KB
00_min_07.txt 1 ms 256 KB
00_min_08.txt 1 ms 256 KB
00_sample_01.txt 1 ms 256 KB
00_sample_02.txt 1 ms 256 KB
00_sample_03.txt 1 ms 256 KB
00_sample_04.txt 1 ms 256 KB
00_sample_05.txt 1 ms 256 KB
01_rnd_00.txt 31 ms 2560 KB
01_rnd_01.txt 35 ms 4220 KB
01_rnd_02.txt 37 ms 7032 KB
01_rnd_03.txt 30 ms 6520 KB
01_rnd_04.txt 36 ms 6520 KB
01_rnd_05.txt 35 ms 2816 KB
01_rnd_06.txt 37 ms 5752 KB
01_rnd_07.txt 37 ms 6904 KB
01_rnd_08.txt 32 ms 2560 KB
01_rnd_09.txt 33 ms 2688 KB
01_rnd_10.txt 38 ms 6776 KB
01_rnd_11.txt 32 ms 2560 KB
01_rnd_12.txt 37 ms 5752 KB
01_rnd_13.txt 38 ms 4220 KB
01_rnd_14.txt 36 ms 4220 KB
01_rnd_15.txt 38 ms 5752 KB
01_rnd_16.txt 32 ms 2560 KB
01_rnd_17.txt 38 ms 5752 KB
01_rnd_18.txt 33 ms 2560 KB
01_rnd_19.txt 32 ms 6776 KB
02_rndhard_00.txt 36 ms 3456 KB
02_rndhard_01.txt 36 ms 3456 KB
02_rndhard_02.txt 36 ms 4220 KB
02_rndhard_03.txt 36 ms 4220 KB
02_rndhard_04.txt 37 ms 4220 KB
02_rndhard_05.txt 37 ms 4220 KB
02_rndhard_06.txt 37 ms 4220 KB
02_rndhard_07.txt 37 ms 4220 KB
02_rndhard_08.txt 36 ms 3456 KB
02_rndhard_09.txt 36 ms 3456 KB
02_rndhard_10.txt 36 ms 3456 KB
02_rndhard_11.txt 35 ms 3456 KB
02_rndhard_12.txt 35 ms 3456 KB
02_rndhard_13.txt 35 ms 3456 KB
02_rndhard_14.txt 36 ms 4220 KB
02_rndhard_15.txt 36 ms 3456 KB
02_rndhard_16.txt 36 ms 4220 KB
02_rndhard_17.txt 36 ms 4220 KB
02_rndhard_18.txt 36 ms 3456 KB
02_rndhard_19.txt 36 ms 3456 KB
02_rndhard_20.txt 36 ms 3456 KB
02_rndhard_21.txt 36 ms 3456 KB
02_rndhard_22.txt 35 ms 3456 KB
02_rndhard_23.txt 35 ms 3456 KB
02_rndhard_24.txt 36 ms 4220 KB
02_rndhard_25.txt 37 ms 4220 KB
02_rndhard_26.txt 36 ms 3456 KB
02_rndhard_27.txt 36 ms 3456 KB
02_rndhard_28.txt 35 ms 3012 KB
02_rndhard_29.txt 35 ms 3012 KB
02_rndhard_30.txt 35 ms 2884 KB
02_rndhard_31.txt 35 ms 3012 KB
02_rndhard_32.txt 37 ms 4220 KB
02_rndhard_33.txt 37 ms 4220 KB
02_rndhard_34.txt 36 ms 4220 KB
02_rndhard_35.txt 37 ms 4220 KB
02_rndhard_36.txt 37 ms 4220 KB
02_rndhard_37.txt 37 ms 4220 KB
02_rndhard_38.txt 37 ms 4220 KB
02_rndhard_39.txt 37 ms 4220 KB
03_rndhardsmall_00.txt 1 ms 256 KB
03_rndhardsmall_01.txt 1 ms 256 KB
03_rndhardsmall_02.txt 1 ms 256 KB
03_rndhardsmall_03.txt 1 ms 256 KB
03_rndhardsmall_04.txt 1 ms 256 KB
03_rndhardsmall_05.txt 1 ms 256 KB
03_rndhardsmall_06.txt 1 ms 256 KB
03_rndhardsmall_07.txt 1 ms 256 KB
03_rndhardsmall_08.txt 1 ms 256 KB
03_rndhardsmall_09.txt 1 ms 256 KB