#1103715 (C++17) No.3199 Key-Door Grid

• 問題: No.3199 Key-Door Grid
• ユーザー: GOTKAKO
• 提出日時: 2025-07-11 21:45:31
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 93 ms / 3,000 ms
• コード長: 1,659 bytes
• コンパイル時間: 1,449 ms
• コンパイル使用メモリ: 231,568 KB
• 実行使用メモリ: 21,504 KB
• 最終ジャッジ日時: 2026-07-13 03:24:01
• 合計ジャッジ時間: 4,559 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 37

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:45:25: warning: 'gx' may be used uninitialized [-Wmaybe-uninitialized]
   45 |     for(auto d : dist.at(gx).at(gy)) if(d != -1) answer = min(answer,d);
      |                  ~~~~~~~^~~~
main.cpp:13:15: note: 'gx' was declared here
   13 |     int sx,sy,gx,gy;
      |               ^~
main.cpp:45:32: warning: 'gy' may be used uninitialized [-Wmaybe-uninitialized]
   45 |     for(auto d : dist.at(gx).at(gy)) if(d != -1) answer = min(answer,d);
      |                  ~~~~~~~~~~~~~~^~~~
main.cpp:13:18: note: 'gy' was declared here
   13 |     int sx,sy,gx,gy;
      |                  ^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/memory_resource.h:49,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/string:72,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bitset:54,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:1:
In constructor 'constexpr std::_Head_base<_Idx, _Head, false>::_Head_base(_UHead&&) [with _UHead = int&; long unsigned int _Idx = 0; _Head = int]',
    inlined from 'constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(_UHead&&, _UTail&& ...) [with _UHead = int&; _UTail = {int&, int}; <template-parameter-2-3> = void; long unsigned int _Idx = 0; _Head = int; _Tail = {int, int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/tuple:315:38,
    inlined from 'constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int&, int}; bool _Valid = true; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = true; _Elements = {int, int, int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/tuple:1490:54,
    inlined from 'int main()' at main.cpp:18:45

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int H,W,M; cin >> H >> W >> M;
    vector<string> S(H);
    for(auto &s : S) cin >> s;

    vector<vector<vector<int>>> dist(H,vector<vector<int>>(W,vector<int>(M+1,-1)));
    int sx,sy,gx,gy;
    for(int i=0; i<H; i++) for(int k=0; k<W; k++){
        if(S.at(i).at(k) == 'S') sx = i,sy = k;
        if(S.at(i).at(k) == 'G') gx = i,gy = k;
    }
    deque<tuple<int,int,int>> Q; Q.push_back({sx,sy,0});
    dist.at(sx).at(sy).at(0) = 0;
    vector<pair<int,int>> dxy = {{-1,0},{0,1},{1,0},{0,-1}};
    while(Q.size()){
        auto [x,y,m] = Q.front(); Q.pop_front();
        int d = dist.at(x).at(y).at(m);
        if('1' <= S.at(x).at(y) && S.at(x).at(y) <= '9'){
            int v = S.at(x).at(y)-'0';
            if(v != m){
                if(dist.at(x).at(y).at(v) != -1) continue;
                dist.at(x).at(y).at(v) = d,Q.push_front({x,y,v});
                continue;
            }
        }

        for(auto [dx,dy] : dxy){
            int nx = x+dx,ny = y+dy;
            if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
            if(S.at(nx).at(ny) == '#') continue;
            if(dist.at(nx).at(ny).at(m) != -1) continue;
            if('a' <= S.at(nx).at(ny) && S.at(nx).at(ny) <= 'i'){
                if(S.at(nx).at(ny)-'a'+1 != m) continue;
            }
            dist.at(nx).at(ny).at(m) = d+1,Q.push_back({nx,ny,m});
        }
    }
    int answer = 10000000;
    for(auto d : dist.at(gx).at(gy)) if(d != -1) answer = min(answer,d);
    if(answer == 10000000) answer = -1;
    cout << answer << endl;
}