結果

問題 No.3199 Key-Door Grid
ユーザー elphe
提出日時 2025-07-12 09:04:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 210 ms / 3,000 ms
コード長 2,239 bytes
コンパイル時間 1,183 ms
コンパイル使用メモリ 109,716 KB
実行使用メモリ 25,216 KB
最終ジャッジ日時 2025-07-12 09:04:39
合計ジャッジ時間 4,420 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <vector>
#include <array>
#include <queue>
#include <tuple>

static inline int_fast32_t solve(const uint_fast32_t H, const uint_fast32_t W, const uint_fast32_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::islower(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]] == '.' || S[i + di[k]][j + dj[k]] == 'S')
							{
								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_fast32_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) << '\n';
	return 0;
}
0