結果

問題 No.3199 Key-Door Grid
ユーザー SHIN KIMURA
提出日時 2025-07-11 23:19:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,553 bytes
コンパイル時間 1,679 ms
コンパイル使用メモリ 138,660 KB
実行使用メモリ 16,072 KB
最終ジャッジ日時 2025-07-11 23:19:49
合計ジャッジ時間 6,375 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2 WA * 1
other TLE * 1 -- * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:175:15: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
  175 |     visited[sx][sy] = true;
      |               ^
main.cpp:164:9: note: ‘sx’ was declared here
  164 |     int sx, sy, gx, gy;
      |         ^~
In file included from /usr/include/c++/13/vector:67,
                 from main.cpp:4:
In member function ‘std::vector<bool, _Alloc>::reference std::vector<bool, _Alloc>::operator[](size_type) [with _Alloc = std::allocator<bool>]’,
    inlined from ‘int main()’ at main.cpp:175:19:
/usr/include/c++/13/bits/stl_bvector.h:1087:23: warning: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized]
 1087 |       { return begin()[__n]; }
      |                ~~~~~~~^
main.cpp: In function ‘int main()’:
main.cpp:164:13: note: ‘sy’ was declared here
  164 |     int sx, sy, gx, gy;
      |             ^~
main.cpp:171:19: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized]
  171 |     que.push({ gx * W + gy,0 });
      |                ~~~^~~
main.cpp:164:17: note: ‘gx’ was declared here
  164 |     int sx, sy, gx, gy;
      |                 ^~
main.cpp:171:23: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized]
  171 |     que.push({ gx * W + gy,0 });
      |                ~~~~~~~^~~~
main.cpp:164:21: note: ‘gy’ was declared here
  164 |     int sx, sy, gx, gy;
      |                     ^~

ソースコード

diff #

//#define _GLIBCXX_DEBUG

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <iterator>
#include <unordered_map>
#include <stack>
#include <string>
#include <cmath>
#include <iomanip>
#include <deque>
#include <unordered_set>
#include <locale>


using namespace std;
using ll = long long;

const ll MOD = 998244353;
const ll MOD2 = 1'000'000'007;

class SegTree {
public:
    vector<ll> dat;
    ll siz = 1;

    SegTree(ll n) {
        while (siz < n) siz *= 2;
        dat.resize(2 * siz, -LLONG_MAX);
    }

    void update(int id, ll x) {
        id += siz;
        dat[id] = x;
        while (id != 0) {
            id /= 2;
            dat[id] = max(dat[2 * id], dat[2 * id + 1]);
        }
    }

    ll getval(int id) {
        return dat[id + siz];
    }

    ll getmax(ll L, ll R, ll a, ll b, ll u) {
        if (b <= L || R <= a) return -LLONG_MAX / 2;
        if (L <= a && b <= R) return dat[u];
        ll m = (a + b) / 2;
        return max(getmax(L, R, a, m, 2 * u),
            getmax(L, R, m, b, 2 * u + 1));
    }
};

class UnionFind {
public:
    vector<int> siz, par;
    UnionFind(int n) {
        siz.assign(n, 1);
        par.assign(n, -1);
    }
    int root(int x) {
        return par[x] == -1 ? x : par[x] = root(par[x]);
    }
    void unite(int x, int y) {
        int rx = root(x), ry = root(y);
        if (rx == ry) return;
        if (siz[rx] < siz[ry]) {
            par[rx] = ry;
            siz[ry] += siz[rx];
        }
        else {
            par[ry] = rx;
            siz[rx] += siz[ry];
        }
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
};

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; if (u < 0) u += m;
    return u;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

//ios::sync_with_stdio(false);
//cin.tie(nullptr);

int H, W, M;

ll add_cost(vector<string> S, int sx, int sy, int gx, int gy) {

    for (int i = 0; i < H; i++)for (int j = 0; j < W; j++)if (S[i][j] != '.')S[i][j] = '#';
    queue<pair<int, int>> que;
    vector<vector<bool>> visited(H, vector<bool>(W, false));
    que.push({ sx * W + sy,0 });
    visited[sx][sy] = true;


    while (!que.empty()) {
        int u = que.front().first, cost = que.front().second;
        int x = u / W, y = u % W;
        que.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];

            if (nx == gx && ny == gy)return cost + 1;

            if (nx < 0 || nx >= H || ny < 0 || W <= ny)continue;
            if (S[nx][ny] == '#' || visited[nx][ny])continue;

            visited[nx][ny] = true;

            que.push({ nx * W + ny,cost + 1 });

        }
    }

    return LLONG_MAX / 4;//たどり着けなかったらめっちゃ増やしとく
}

int main() {
    //ゴールからスタートしてBFSでゴールを目指す
    //途中で扉に引っかかったら
    //扉から対応する鍵まで行く道の最短経路+スタートから鍵までの最短距離 を計算する

    cin >> H >> W >> M;
    vector<string> S(H);
    for (int i = 0; i < H; i++)cin >> S[i];
    map<char, int> keyx, keyy;
    for (int i = 1; i <= 9; i++) {
        keyx[i] = -1, keyy[i] = -1;
    }

    for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
        if (!('1' <= S[i][j] && S[i][j] <= '9'))continue;
        keyx[S[i][j] - '1' + 'a'] = i, keyy[S[i][j] - '1' + 'a'] = j;
    }

    int sx, sy, gx, gy;
    for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
        if (S[i][j] == 'S')sx = i, sy = j;
        if (S[i][j] == 'G')gx = i, gy = j;
    }

    queue<pair<int, int>> que;
    que.push({ gx * W + gy,0 });

    ll ans = LLONG_MAX / 2;
    vector<vector<bool>> visited(H, vector<bool>(W, false));
    visited[sx][sy] = true;

    while (!que.empty()) {
        int u = que.front().first;
        ll cost = que.front().second;
        int x = u / W, y = u % W;

        que.pop();

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];



            if (nx < 0 || H <= nx || ny < 0 || W <= ny)continue;//範囲外ならやめる

            if (S[nx][ny] == 'S') {//ゴール着いたら出力する
                cout << min(ans, cost + 1) << endl;
                return 0;
            }

            if (S[nx][ny] == '#')continue;
            if (visited[nx][ny])continue;

            visited[nx][ny] = true;

            if (islower(S[nx][ny])) {//扉に来たら
                ll C = cost + 1;
                //cout << cost << endl;
                //cout << "check:" << add_cost(S, nx, ny, keyx[S[nx][ny]], keyy[S[nx][ny]]) << " " << add_cost(S, keyx[S[nx][ny]], keyy[S[nx][ny]], sx, sy) << endl;
                C += add_cost(S, nx, ny, keyx[S[nx][ny]], keyy[S[nx][ny]]) + add_cost(S, keyx[S[nx][ny]], keyy[S[nx][ny]], sx, sy);

                ans = min(ans, C);

                continue;//queにはくわえずそのままスルー
            }

            //扉以外(道か鍵)のマスに来た時


            que.push({ nx * W + ny,cost + 1 });
        }
    }

    cout << (ans < LLONG_MAX / 8 ? ans : -1) << endl;

}
0