結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-12 09:00:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,197 bytes |
コンパイル時間 | 1,610 ms |
コンパイル使用メモリ | 111,224 KB |
実行使用メモリ | 25,216 KB |
最終ジャッジ日時 | 2025-07-12 09:00:57 |
合計ジャッジ時間 | 4,452 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 WA * 2 |
ソースコード
#include <iostream> #include <cstdint> #include <vector> #include <array> #include <queue> #include <tuple> static inline int_fast32_t solve(const uint_fast16_t H, const uint_fast16_t W, const uint_fast16_t M, const std::vector<std::string>& S) noexcept { std::vector<std::vector<std::vector<uint_fast32_t>>> dist(M + 1, std::vector<std::vector<uint_fast32_t>>(H, std::vector<uint_fast32_t>(W, UINT_FAST32_MAX))); std::queue<std::tuple<uint_fast32_t, uint_fast32_t, uint_fast32_t>> q; for (uint_fast32_t i = 0; i != H; ++i) for (uint_fast32_t j = 0; j != W; ++j) if (S[i][j] == 'S') { dist[0][i][j] = 0, q.emplace(0, i, j); while (!q.empty()) { constexpr std::array<uint_fast32_t, 4> di = { UINT_FAST32_MAX, 0, 0, 1 }, dj = { 0, UINT_FAST32_MAX, 1, 0 }; const auto& [layer, i, j] = q.front(); for (uint_fast32_t k = 0; k != di.size(); ++k) if (i + di[k] < H && j + dj[k] < W) { if (S[i + di[k]][j + dj[k]] == 'G') return dist[layer][i][j] + 1; else if (std::isdigit(S[i + di[k]][j + dj[k]])) { if (dist[S[i + di[k]][j + dj[k]] - '0'][i + di[k]][j + dj[k]] == UINT_FAST32_MAX) dist[S[i + di[k]][j + dj[k]] - '0'][i + di[k]][j + dj[k]] = dist[layer][i][j] + 1, q.emplace(S[i + di[k]][j + dj[k]] - '0', i + di[k], j + dj[k]); } else if (std::isalpha(S[i + di[k]][j + dj[k]])) { if (layer == S[i + di[k]][j + dj[k]] - ('a' - 1) && dist[layer][i + di[k]][j + dj[k]] == UINT_FAST32_MAX) dist[layer][i + di[k]][j + dj[k]] = dist[layer][i][j] + 1, q.emplace(layer, i + di[k], j + dj[k]); } else if (S[i + di[k]][j + dj[k]] == '.') { if (dist[layer][i + di[k]][j + dj[k]] == UINT_FAST32_MAX) dist[layer][i + di[k]][j + dj[k]] = dist[layer][i][j] + 1, q.emplace(layer, i + di[k], j + dj[k]); } } q.pop(); } return -1; } return -1; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast16_t H, W, M, i; std::cin >> H >> W >> M; std::vector<std::string> S(H); for (i = 0; i != H; ++i) S[i].reserve(W), std::cin >> S[i]; std::cout << solve(H, W, M, S); return 0; }