結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:53:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 3,000 ms |
コード長 | 2,861 bytes |
コンパイル時間 | 3,601 ms |
コンパイル使用メモリ | 295,876 KB |
実行使用メモリ | 21,632 KB |
最終ジャッジ日時 | 2025-07-11 21:53:35 |
合計ジャッジ時間 | 7,006 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:106:27: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized] 106 | chmin(ans, dist[gi][gj][k]); | ^ main.cpp:53:17: note: ‘gi’ was declared here 53 | int si, sj, gi, gj; | ^~ main.cpp:106:31: warning: ‘gj’ may be used uninitialized [-Wmaybe-uninitialized] 106 | chmin(ans, dist[gi][gj][k]); | ^ main.cpp:53:21: note: ‘gj’ was declared here 53 | int si, sj, gi, gj; | ^~ In file included from /usr/include/c++/13/bits/uses_allocator_args.h:38, from /usr/include/c++/13/bits/memory_resource.h:41, 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 ‘constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = tuple<int, int, int>; _Args = {int&, int&, int}]’ at /usr/include/c++/13/bits/stl_construct.h:97:14, inlined from ‘static constexpr void std::allocato
ソースコード
#include <bits/stdc++.h> using namespace std; #define For(i, a, b) for(int i = (a); i < (b); i++) #define rep(i, n) For(i, 0, n) #define rFor(i, a, b) for(int i = (a); i >= (b); i--) #define ALL(v) (v).begin(), (v).end() #define rALL(v) (v).rbegin(), (v).rend() #define SZ(v) ((int)(v).size()) using lint = long long; using ld = long double; int INF = 2000000000; lint LINF = 1000000000000000000; struct SetupIo { SetupIo() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); } } setupio; // a <- max(a, b) template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } // a <- min(a, b) template <class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } vector<int> di = {0, 0, -1, 1}; vector<int> dj = {-1, 1, 0, 0}; int main() { int H, W, M; cin >> H >> W >> M; vector<vector<char>> S(H, vector<char>(W)); int si, sj, gi, gj; rep(i, H) { rep(j, W) { cin >> S[i][j]; if (S[i][j] == 'S') { si = i; sj = j; } if (S[i][j] == 'G') { gi = i; gj = j; } } } auto inside = [&](int i, int j) -> bool { return (0 <= i && i < H && 0 <= j && j < W); }; // dist[i][j][k]:= 鍵 k を持った状態で (i, j) に到達 vector<vector<vector<int>>> dist(H, vector<vector<int>>(W, vector<int>(M + 1, INF))); queue<tuple<int, int, int>> q; dist[si][sj][0] = 0; q.emplace(si, sj, 0); while (!q.empty()) { auto [i, j, k] = q.front(); q.pop(); rep(kk, 4) { int ni = i + di[kk], nj = j + dj[kk]; if (!inside(ni, nj) || S[ni][nj] == '#') { continue; } if (S[ni][nj] == '.' || S[ni][nj] == 'S' || S[ni][nj] == 'G') { int nk = k; if (chmin(dist[ni][nj][nk], dist[i][j][k] + 1)) { q.emplace(ni, nj, nk); } } else if ('1' <= S[ni][nj] && S[ni][nj] <= '9') { int nk = S[ni][nj] - '0'; if (chmin(dist[ni][nj][nk], dist[i][j][k] + 1)) { q.emplace(ni, nj, nk); } } else { int x = S[ni][nj] - 'a' + 1; if (k == x) { int nk = k; if (chmin(dist[ni][nj][nk], dist[i][j][k] + 1)) { q.emplace(ni, nj, nk); } } } } } int ans = INF; rep(k, M + 1) { chmin(ans, dist[gi][gj][k]); } cout << (ans != INF ? ans : -1) << "\n"; }