結果

問題 No.3199 Key-Door Grid
ユーザー GOTKAKO
提出日時 2025-07-11 21:45:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 161 ms / 3,000 ms
コード長 1,659 bytes
コンパイル時間 2,543 ms
コンパイル使用メモリ 213,936 KB
実行使用メモリ 21,504 KB
最終ジャッジ日時 2025-07-11 21:45:40
合計ジャッジ時間 6,185 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 /usr/include/c++/13/bits/memory_resource.h:47,
                 from /usr/include/c++/13/string:58,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 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 /usr/include/c++/13/tuple:293: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 /usr/include/c++/13/tuple:891:54,
    inlined from ‘int main()’ at main.cpp:18:45:
/usr/include/c++/13/tuple:201:11: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
  201 |         : _M_head_impl(std::forward<_UHead>(__h)) { }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ma

ソースコード

diff # 

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