結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 22:03:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 138 ms / 3,000 ms |
コード長 | 2,302 bytes |
コンパイル時間 | 2,056 ms |
コンパイル使用メモリ | 176,744 KB |
実行使用メモリ | 21,504 KB |
最終ジャッジ日時 | 2025-07-11 22:03:33 |
合計ジャッジ時間 | 5,570 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:37:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 37 | auto [i, j, k] = que.front(); que.pop(); | ^ main.cpp:63:19: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized] 63 | if(dist[gi][gj][i] == -1) continue; | ^ main.cpp:22:17: note: ‘gi’ was declared here 22 | int si, sj, gi, gj; | ^~ main.cpp:63:23: warning: ‘gj’ may be used uninitialized [-Wmaybe-uninitialized] 63 | if(dist[gi][gj][i] == -1) continue; | ^ main.cpp:22:21: note: ‘gj’ was declared here 22 | int si, sj, gi, gj; | ^~
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; void solve(){ int h, w, m; cin >> h >> w >> m; vector<string> s(h); for(int i=0; i<h; i++) cin >> s[i]; int si, sj, gi, gj; for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ if(s[i][j] == 'S') si = i, sj = j; if(s[i][j] == 'G') gi = i, gj = j; } } vector<vector<vector<int>>> dist(h, vector<vector<int>>(w, vector<int>(m+1, -1))); queue<tuple<int, int, int>> que; dist[si][sj][m] = 0; que.emplace(si, sj, m); int di[4] = {1, 0, -1, 0}; int dj[4] = {0, 1, 0, -1}; while(!que.empty()){ auto [i, j, k] = que.front(); que.pop(); for(int d=0; d<4; d++){ int ni = i + di[d]; int nj = j + dj[d]; if(ni < 0 || ni >= h || nj < 0 || nj >= w) continue; if(s[ni][nj] == '#') continue; if('a' <= s[ni][nj] && s[ni][nj] <= 'z'){ if(k != (int)(s[ni][nj]-'a')) continue; if(dist[ni][nj][k] != -1) continue; dist[ni][nj][k] = dist[i][j][k] + 1; que.emplace(ni, nj, k); }else if('1' <= s[ni][nj] && s[ni][nj] <= '9'){ if(dist[ni][nj][s[ni][nj]-'0'-1] != -1) continue; dist[ni][nj][s[ni][nj]-'0'-1] = dist[i][j][k] + 1; que.emplace(ni, nj, (int)(s[ni][nj]-'0')-1); }else{ if(dist[ni][nj][k] != -1) continue; dist[ni][nj][k] = dist[i][j][k] + 1; que.emplace(ni, nj, k); } } } int ans = -1; for(int i=0; i<=m; i++){ if(dist[gi][gj][i] == -1) continue; if(ans == -1 || ans > dist[gi][gj][i]) ans = dist[gi][gj][i]; } cout << ans << endl; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int T=1; //cin >> T; while(T--) solve(); }