結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-12 03:39:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 604 ms / 3,000 ms |
コード長 | 7,867 bytes |
コンパイル時間 | 2,445 ms |
コンパイル使用メモリ | 208,128 KB |
実行使用メモリ | 149,988 KB |
最終ジャッジ日時 | 2025-07-12 03:40:12 |
合計ジャッジ時間 | 12,854 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define drep_(i, a_, b_, a, b, ...) for (int i = (a) - 1, lim##i = (b); i >= lim##i; --i) #define drep(i, ...) drep_(i, __VA_ARGS__, __VA_ARGS__, __VA_ARGS__, 0) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #ifdef LOCAL void debug_out() { cerr << endl; } template <class Head, class... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); } #define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif using ll = long long; using ld = long double; template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; template <class T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); } template <class... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); } template <class T> inline void fin(const T x) { cout << x << '\n'; exit(0); } template <class T> inline void deduplicate(vector<T> &a) { sort(all(a)); a.erase(unique(all(a)), a.end()); } template <class T> inline bool chmin(T &a, const T b) { if (a > b) { a = b; return true; } return false; } template <class T> inline bool chmax(T &a, const T b) { if (a < b) { a = b; return true; } return false; } template <class T> inline int sz(const T &x) { return x.size(); } template <class T> inline int count_between(const vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } template <class T1, class T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template <class T1, class T2> ostream &operator<<(ostream &os, pair<T1, T2> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; } template <class T, size_t n> istream &operator>>(istream &is, array<T, n> &v) { for (auto &e : v) is >> e; return is; } template <class T, size_t n> ostream &operator<<(ostream &os, array<T, n> &v) { for (auto &e : v) os << e << ' '; return os; } template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; } template <class T> ostream &operator<<(ostream &os, vector<T> &v) { for (auto &e : v) os << e << ' '; return os; } template <class T> istream &operator>>(istream &is, deque<T> &v) { for (auto &e : v) is >> e; return is; } template <class T> ostream &operator<<(ostream &os, deque<T> &v) { for (auto &e : v) os << e << ' '; return os; } inline ll floor_div(ll x, ll y) { if (y < 0) x = -x, y = -y; return x >= 0 ? x / y : (x - y + 1) / y; } inline ll ceil_div(ll x, ll y) { if (y < 0) x = -x, y = -y; return x >= 0 ? (x + y - 1) / y : x / y; } inline int floor_log2(const ll x) { assert(x > 0); return 63 - __builtin_clzll(x); } inline int ceil_log2(const ll x) { assert(x > 0); return (x == 1) ? 0 : 64 - __builtin_clzll(x - 1); } inline int popcount(const ll x) { return __builtin_popcountll(x); } struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios; // 時間計測 auto system_now = std::chrono::system_clock::now(); int check_time() { auto now = std::chrono::system_clock::now(); return std::chrono::duration_cast<std::chrono::milliseconds>(now - system_now).count(); } // 乱数 struct Xorshift { uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123; uint32_t rand_int() { uint32_t t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } // 0以上mod未満の整数を乱択 uint32_t rand_int(uint32_t mod) { return rand_int() % mod; } // l以上r未満の整数を乱択 uint32_t rand_int(uint32_t l, uint32_t r) { assert(l < r); return l + rand_int(r - l); } // 0以上1以下の実数を乱沢 double rand_double() { return (double)rand_int() / UINT32_MAX; } }; Xorshift xor_shift; // constexpr int INF = numeric_limits<int>::max() >> 2; // constexpr ll INFll = numeric_limits<ll>::max() >> 2; // constexpr ld EPS = 1e-10; // const ld PI = acos(-1.0); // using mint = modint998244353; // using mint = modint1000000007; // using mint = modint; // using Vm = V<mint>; using VVm = VV<mint>; int main() { int H, W, M; cin >> H >> W >> M; vector<string> S(H); rep(i, H) { cin >> S[i]; } // 各状態は,(i, j, k) で表される // i: 現在の行 // j: 現在の列 // k: 現在の状態 (0 <= k <= M) auto encode = [&](int i, int j, int k) { return (i * W + j) * (M + 1) + k; }; auto decode = [&](int x) { int k = x % (M + 1); x /= (M + 1); int j = x % W; int i = x / W; return make_tuple(i, j, k); }; vector<vector<int>> G(H * W * (M + 1)); auto is_key = [&](char c) { if ('1' <= c && c <= '9') { return c - '1'; } else { return -1; } }; auto is_door = [&](char c) { if ('a' <= c && c <= 'i') { return c - 'a'; } else { return -1; } }; auto in_bounds = [&](int i, int j) { return 0 <= i && i < H && 0 <= j && j < W; }; vector<int> dx = {0, 1, 0, -1}; vector<int> dy = {1, 0, -1, 0}; rep(idx, H * W * (M + 1)) { auto [i, j, k] = decode(idx); if (S[i][j] == '#') { continue; } else { rep(dir, 4) { int ni = i + dx[dir]; int nj = j + dy[dir]; if (!in_bounds(ni, nj)) continue; if (S[ni][nj] == '#') { continue; } else if (S[ni][nj] == '.' or S[ni][nj] == 'S' or S[ni][nj] == 'G') { int next_idx = encode(ni, nj, k); G[idx].push_back(next_idx); } else if (is_key(S[ni][nj]) != -1) { int key = is_key(S[ni][nj]); int next_ix = encode(ni, nj, key + 1); G[idx].push_back(next_ix); } else if (is_door(S[ni][nj]) != -1) { int door = is_door(S[ni][nj]); if (k == door + 1) { int next_ix = encode(ni, nj, k); G[idx].push_back(next_ix); } } } } } int si = -1, sj = -1; int gi = -1, gj = -1; rep(i, H) { rep(j, W) { if (S[i][j] == 'S') { si = i; sj = j; } else if (S[i][j] == 'G') { gi = i; gj = j; } } } int start = encode(si, sj, 0); // グラフG上のBFSで距離を求める vector<int> dist(H * W * (M + 1), -1); queue<int> que; que.push(start); dist[start] = 0; while (!que.empty()) { int v = que.front(); que.pop(); for (int nv : G[v]) { if (dist[nv] == -1) { dist[nv] = dist[v] + 1; que.push(nv); } } } int ans = INT_MAX; rep(k, M + 1) { int v = encode(gi, gj, k); if (dist[v] != -1) { chmin(ans, dist[v]); } } cout << (ans == INT_MAX ? -1 : ans) << '\n'; return 0; }