結果

問題 No.3199 Key-Door Grid
ユーザー 北杜
提出日時 2025-07-11 23:05:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 517 ms / 3,000 ms
コード長 2,112 bytes
コンパイル時間 9,339 ms
コンパイル使用メモリ 389,096 KB
実行使用メモリ 17,664 KB
最終ジャッジ日時 2025-07-11 23:06:09
合計ジャッジ時間 15,894 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:42:20: warning: ‘si’ may be used uninitialized [-Wmaybe-uninitialized]
   42 |     st.i = 0; st.j = si; st.k = sj;
      |               ~~~~~^~~~
main.cpp:36:9: note: ‘si’ was declared here
   36 |     int si, sj;
      |         ^~
main.cpp:42:31: warning: ‘sj’ may be used uninitialized [-Wmaybe-uninitialized]
   42 |     st.i = 0; st.j = si; st.k = sj;
      |                          ~~~~~^~~~
main.cpp:36:13: note: ‘sj’ was declared here
   36 |     int si, sj;
      |             ^~

ソースコード

diff # 

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define rep(i, n) for (int i = 0; i < (ll)(n); i++)
#define all(a) (a).begin(), (a).end()
using ll = long long;
const int INF32 = 2e9;
const ll INF64 = 4e18;

const vector<int> dx = {1, 0, -1, 0},
                  dy = {0, 1, 0, -1};

void printYN(bool ok){
    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
    return;
}

struct iti {
    int i, j, k;
};

int main() {
    int H, W, M;
    cin >> H >> W >> M;
    vector<string> S(H);
    rep(i, H)cin >> S[i];
    vector<vector<string>> G(M+1);
    rep(i, M+1){
        G[i] = S;
    }
    int si, sj;
    rep(i, H)rep(j, W)if(G[0][i][j]=='S'){
        si = i, sj = j;
    }
    queue<iti> q;
    iti st;
    st.i = 0; st.j = si; st.k = sj;
    q.push(st);
    vector<vector<vector<int>>> dist(M+1, vector<vector<int>>(H, vector<int>(W, INF32)));
    dist[0][si][sj] = 0;
    while(!q.empty()){
        iti now = q.front();
        q.pop();
        rep(l, dx.size()){
            int ni = now.i;
            int nj = now.j + dx[l], nk = now.k + dy[l];
            if(nj<0||H<=nj||nk<0||W<=nk)continue;
            if(G[ni][nj][nk]=='#')continue;
            if(G[ni][nj][nk]>='a'&&G[ni][nj][nk]<'j'&&G[ni][nj][nk]!='a'+ni-1)continue;
            if(G[ni][nj][nk]>='1'&&G[ni][nj][nk]<='9'){
                ni = G[ni][nj][nk] - '0';
                if(dist[ni][nj][nk]!=INF32)continue;
                dist[ni][nj][nk] = dist[now.i][now.j][now.k]+1;
                iti next;
                next.i = ni; next.j = nj; next.k = nk;
                q.push(next);
            } else {
                if(dist[ni][nj][nk]!=INF32)continue;
                dist[ni][nj][nk] = dist[now.i][now.j][now.k]+1;
                iti next;
                next.i = ni; next.j = nj; next.k = nk;
                q.push(next);
            }
        }
    }
    int ans = INF32;
    rep(i, M+1)rep(j, H)rep(k, W)if(G[i][j][k]=='G')ans = min(dist[i][j][k], ans);
    if(ans!=INF32)cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}
0