結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-13 16:26:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 3,000 ms |
コード長 | 2,076 bytes |
コンパイル時間 | 6,839 ms |
コンパイル使用メモリ | 482,212 KB |
実行使用メモリ | 21,760 KB |
最終ジャッジ日時 | 2025-07-13 16:26:31 |
合計ジャッジ時間 | 11,595 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; using Bint = mp::cpp_int; using namespace std; using namespace atcoder; #define rep(i, n) for(int i=0;i<(n);++i) #define rep1(i, n) for(int i=1;i<=(n);i++) #define ll long long using mint = modint998244353; using P = pair<ll,ll>; using lb = long double; using T = tuple<ll, ll, ll>; #ifdef LOCAL # include <debug_print.hpp> # define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define dbg(...) (static_cast<void>(0)) #endif int main() { int h, w, m; cin >> h >> w >> m; vector<string> s(h); rep(i,h) cin >> s[i]; const int INF = 1e9; vector<vector<vector<int>>> dist(h, vector<vector<int>>(w, vector<int>(m+1, INF))); queue<tuple<int, int, int>> q; rep(i,h)rep(j,w) { if(s[i][j]=='S') { dist[i][j][0] = 0; q.emplace(i,j,0); } } vector<int> di = {0, -1, 0, 1}; vector<int> dj = {-1, 0, 1, 0}; while(!q.empty()) { auto [i,j,k] = q.front();q.pop(); dbg(i,j,k); rep(d,4) { int ni = i + di[d]; int nj = j + dj[d]; int nk = k; if(ni<0 || ni>=h || nj<0 || nj>=w) continue; if(s[ni][nj]=='#') continue; if(s[ni][nj]=='.' || s[ni][nj]=='G' || s[ni][nj]=='S') { } else if(s[ni][nj]>='1' && s[ni][nj]<='9') { nk = s[ni][nj] - '0'; } else{ if(s[ni][nj]-'a'!=k-1) continue; } if(dist[ni][nj][nk]>dist[i][j][k]+1) { dbg(nk,s[ni][nj]); dist[ni][nj][nk] = dist[i][j][k]+1; q.emplace(ni,nj,nk); } } } int ans = INF; rep(i,h)rep(j,w) { if(s[i][j]=='G') { rep(k,m+1) ans = min(ans, dist[i][j][k]); } } if(ans==INF) ans = -1; cout << ans << endl; return 0; }