結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 23:11:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 3,000 ms |
コード長 | 1,637 bytes |
コンパイル時間 | 3,191 ms |
コンパイル使用メモリ | 290,744 KB |
実行使用メモリ | 21,504 KB |
最終ジャッジ日時 | 2025-07-11 23:12:12 |
合計ジャッジ時間 | 6,465 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include <atcoder/modint> // using namespace atcoder; // using mint = modint998244353; using ll = long long; #define fix(x) fixed << setprecision(x) #define rep(i, n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;} constexpr ll INFLL = (1LL << 62), MOD = 998244353; constexpr int INF = (1 << 30); int H[] = {0,1,0,-1}, W[] = {1,0,-1,0}; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int h,w,m; cin >> h >> w >> m; vector<string> s(h); int sh = -1, sw = -1, gh = -1, gw = -1; rep(i,h){ cin >> s[i]; rep(j,w){ if(s[i][j]=='S') sh = i, sw = j; if(s[i][j]=='G') gh = i, gw = j; } } vector dist(h,vector(w,vector<int>(m+1,INF))); dist[sh][sw][m] = 0; queue<tuple<int,int,int>> que; que.emplace(sh,sw,m); while(que.size()){ auto [p,q,x] = que.front(); que.pop(); rep(i,4){ int np = p+H[i], nq = q+W[i]; if(np<0 || np>=h || nq<0 || nq>=w || s[np][nq]=='#') continue; if(s[np][nq]>='a' && s[np][nq]<='i' && s[np][nq]-'a'!=x) continue; int y = x; if(s[np][nq]>='1' && s[np][nq]<='9') y = s[np][nq] - '1'; if(chmin(dist[np][nq][y], dist[p][q][x]+1)) que.emplace(np,nq,y); } } int ans = INF; rep(i,m+1) chmin(ans, dist[gh][gw][i]); if(ans==INF) ans = -1; cout << ans << '\n'; return 0; }