結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:56:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 287 ms / 3,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 6,462 ms |
コンパイル使用メモリ | 334,288 KB |
実行使用メモリ | 25,472 KB |
最終ジャッジ日時 | 2025-07-11 22:56:48 |
合計ジャッジ時間 | 9,934 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:56:38: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized] 56 | rep(i, m + 1) chmin(ans, d.at(i).at(gi).at(gj)); | ~~~~~~~~~~^~~~ main.cpp:26:15: note: ‘gi’ was declared here 26 | int si, sj, gi, gj; | ^~ main.cpp:56:45: warning: ‘gj’ may be used uninitialized [-Wmaybe-uninitialized] 56 | rep(i, m + 1) chmin(ans, d.at(i).at(gi).at(gj)); | ~~~~~~~~~~~~~~~~~^~~~ main.cpp:26:19: note: ‘gj’ was declared here 26 | int si, sj, gi, gj; | ^~ main.cpp:39:13: warning: ‘si’ may be used uninitialized [-Wmaybe-uninitialized] 39 | d.at(0).at(si).at(sj) = 0; | ~~~~~~~~~~^~~~ main.cpp:26:7: note: ‘si’ was declared here 26 | int si, sj, gi, gj; | ^~ main.cpp:39:20: warning: ‘sj’ may be used uninitialized [-Wmaybe-uninitialized] 39 | d.at(0).at(si).at(sj) = 0; | ~~~~~~~~~~~~~~~~~^~~~ main.cpp:26:11: note: ‘sj’ was declared here 26 | int si, sj, gi, gj; | ^~
ソースコード
#if __has_include(<yoniha/all.h>) #include <yoniha/all.h> using namespace atcoder; #else #include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif #endif using namespace std; #define int long long #define all(x) (x).begin(), (x).end() #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for(int i = (int)(n - 1); i >= 0; i--) template <typename T> bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template <typename T> bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} // using mint = modint; signed main(){ int h, w, m; cin >> h >> w >> m; vector<string> s(h); for(auto&& si : s) cin >> si; int si, sj, gi, gj; rep(i, h) rep(j, w){ if(s.at(i).at(j) == 'S'){ si = i; sj = j; } if(s.at(i).at(j) == 'G'){ gi = i; gj = j; } } const int inf = 1ll << 60; vector d(m + 1, vector(h, vector(w, inf))); deque<tuple<int, int, int, int>> bfs; // 鍵番号、i、j、距離 d.at(0).at(si).at(sj) = 0; bfs.emplace_back(0, si, sj, 0); while(!bfs.empty()){ auto [fkey, fi, fj, fd] = bfs.front(); bfs.pop_front(); for(auto [di, dj] : vector<pair<int, int>>{{-1, 0}, {0, -1}, {0, 1}, {1, 0}}){ int tkey = fkey, ti = fi + di, tj = fj + dj, td = fd + 1; if(ti < 0 || ti >= h || tj < 0 || tj >= w) continue; if(s.at(ti).at(tj) == '#') continue; if(islower(s.at(ti).at(tj)) && fkey != s.at(ti).at(tj) - 'a' + 1) continue; if(isdigit(s.at(ti).at(tj))) tkey = s.at(ti).at(tj) - '0'; if(d.at(tkey).at(ti).at(tj) != inf) continue; d.at(tkey).at(ti).at(tj) = td; bfs.emplace_back(tkey, ti, tj, td); } } int ans = inf; rep(i, m + 1) chmin(ans, d.at(i).at(gi).at(gj)); cout << (ans == inf ? -1ll : ans) << '\n'; }