結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 22:31:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 206 ms / 3,000 ms |
コード長 | 1,635 bytes |
コンパイル時間 | 4,307 ms |
コンパイル使用メモリ | 260,844 KB |
実行使用メモリ | 83,116 KB |
最終ジャッジ日時 | 2025-07-11 22:32:05 |
合計ジャッジ時間 | 7,912 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template <class T> bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template <class T> bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; #include <atcoder/all> // template atcoder segtree using S = ll; S op(S a, S b) { return max(a, b); } S e() { return -1e18; } using segtree = atcoder::segtree<S, op, e>; void solve() { int h, w, m; cin >> h >> w >> m; vector<string> s(h); rep(i, 0, h) cin >> s[i]; vector dp(h, vector(w, vector<ll>(m + 1, 1e18))); vector<array<int, 3>> q; { rep(i, 0, h) rep(j, 0, w) { if (s[i][j] == 'S') { dp[i][j][0] = 0; q.push_back({(int)i, (int)j, 0}); } } } vector<int> dd = {0, 1, 0, -1, 0}; rep(lp, 0, q.size()) { auto [x, y, k] = q[lp]; rep(d, 0, 4) { int nx = x + dd[d]; int ny = y + dd[d + 1]; if (nx < 0 || h <= nx || ny < 0 || w <= ny) continue; if (s[nx][ny] == '#') continue; if (s[nx][ny] == 'G') { cout << dp[x][y][k] + 1 << "\n"; return; } int nk = k; if ('a' <= s[nx][ny] && s[nx][ny] <= 'i') { if (s[nx][ny] - 'a' != k - 1) continue; } else if ('0' <= s[nx][ny] && s[nx][ny] <= '9') { nk = s[nx][ny] - '0'; } if (chmin(dp[nx][ny][nk], dp[x][y][k] + 1)) { q.push_back({nx, ny, nk}); } } } cout << "-1\n"; } int main() { int t = 1; // cin >> t; while (t--) solve(); }