結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 21:48:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 3,000 ms |
コード長 | 2,221 bytes |
コンパイル時間 | 3,278 ms |
コンパイル使用メモリ | 290,740 KB |
実行使用メモリ | 21,760 KB |
最終ジャッジ日時 | 2025-07-11 21:48:17 |
合計ジャッジ時間 | 6,407 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:69:27: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized] 69 | rep(k,0,m+1) if (dist[gi][gj][k] != -1) ans = min(ans, dist[gi][gj][k]); | ^ main.cpp:30:15: note: ‘gi’ was declared here 30 | int si, sj, gi, gj; | ^~ main.cpp:69:31: warning: ‘gj’ may be used uninitialized [-Wmaybe-uninitialized] 69 | rep(k,0,m+1) if (dist[gi][gj][k] != -1) ans = min(ans, dist[gi][gj][k]); | ^ main.cpp:30:19: note: ‘gj’ was declared here 30 | int si, sj, gi, gj; | ^~ In file included from /usr/include/c++/13/bits/stl_algobase.h:64, from /usr/include/c++/13/algorithm:60, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51, from main.cpp:1: In constructor ‘constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = int&; _U2 = int&; _T1 = int; _T2 = int]’, inlined from ‘int main()’ at main.cpp:36:15: /usr/include/c++/13/bits/stl_pair.h:317:11: warning: ‘si’ may be used uninitialized [-Wmaybe-uninitialized] 317 | : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:30:7: note: ‘si’ was declared here 30 | int si, sj, gi, gj; | ^~ In constructor ‘constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = int&; _U2 = int&; _T1 = int; _T2 = int]’, inlined from ‘int main()’ at main.cpp:36:15: /usr/include/c++/13/bits/stl_pair.h:317:42: warning: ‘sj’ may be used uninitialized [-Wmaybe-uninitialized] 317 | : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:30:11: note: ‘sj’ was declared here 30 | int s
ソースコード
#include <bits/stdc++.h> #define fi first #define se second #define rep(i,s,n) for (int i = (s); i < (n); ++i) #define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define len(x) (int)(x).size() #define dup(x,y) (((x)+(y)-1)/(y)) #define pb push_back #define eb emplace_back #define Field(T) vector<vector<T>> using namespace std; using ll = long long; using ull = unsigned long long; template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>; using P = pair<int,int>; template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;} int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main() { int h, w, m; cin >> h >> w >> m; vector<string> s(h); rep(i,0,h) cin >> s[i]; vector<vector<vector<int>>> dist(h, vector<vector<int>>(w, vector<int>(m+1, -1))); int si, sj, gi, gj; rep(i,0,h) rep(j,0,w) { if (s[i][j] == 'S') si = i, sj = j; if (s[i][j] == 'G') gi = i, gj = j; } queue<pair<P,int>> que; que.emplace(P{si, sj}, m); dist[si][sj][m] = 0; while(!que.empty()) { P p; int k; tie(p, k) = que.front(); que.pop(); int x = p.fi, y = p.se; // cout << x << " " << y << endl; rep(d,0,4) { int nx = x+dx[d], ny = y+dy[d]; if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue; if (s[nx][ny] == '#') continue; if ('a' <= s[nx][ny] && s[nx][ny] <= 'i') { if (s[nx][ny]-'a' != k) continue; if (dist[nx][ny][k] == -1) { dist[nx][ny][k] = dist[x][y][k]+1; que.emplace(P{nx, ny}, k); } } else if ('1' <= s[nx][ny] && s[nx][ny] <= '9') { int nk = s[nx][ny]-'1'; if (dist[nx][ny][nk] == -1) { dist[nx][ny][nk] = dist[x][y][k]+1; que.emplace(P{nx, ny}, nk); } } else { if (dist[nx][ny][k] == -1) { dist[nx][ny][k] = dist[x][y][k]+1; que.emplace(P{nx, ny}, k); } } } } int ans = 1000000000; rep(k,0,m+1) if (dist[gi][gj][k] != -1) ans = min(ans, dist[gi][gj][k]); if (ans == 1000000000) ans = -1; cout << ans << endl; return 0; }