結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー eve__fuyuki
提出日時 2025-07-12 20:00:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 120 ms / 3,000 ms
コード長 1,722 bytes
コンパイル時間 2,285 ms
コンパイル使用メモリ 210,312 KB
実行使用メモリ 21,504 KB
最終ジャッジ日時 2025-07-12 20:00:42
合計ジャッジ時間 5,522 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

void fast_io() {
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
}

int main() {
	fast_io();
	int h, w, m;
	cin >> h >> w >> m;
	vector<string> s(h);
	for (int i = 0; i < h; i++) {
		cin >> s[i];
	}
	const int INF = 1e9;
	vector dist(h, vector(w, vector<int>(m + 1, INF)));
	deque<tuple<int, int, int>> dq;
	int gi = -1, gj = -1;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == 'S') {
				dist[i][j][0] = 0;
				dq.emplace_back(i, j, 0);
			} else if (s[i][j] == 'G') {
				gi = i;
				gj = j;
			}
		}
	}
	int di[] = {1, -1, 0, 0};
	int dj[] = {0, 0, 1, -1};
	auto is_in = [&](int i, int j) {
		return i >= 0 && i < h && j >= 0 && j < w;
	};
	while (!dq.empty()) {
		auto [i, j, key] = dq.front();

		dq.pop_front();
		for (int d = 0; d < 4; d++) {
			int ni = i + di[d];
			int nj = j + dj[d];
			if (!is_in(ni, nj) || s[ni][nj] == '#') continue;
			if ('1' <= s[ni][nj] && s[ni][nj] <= '9') {
				int nkey = s[ni][nj] - '0';
				if (dist[ni][nj][nkey] > dist[i][j][key] + 1) {
					dist[ni][nj][nkey] = dist[i][j][key] + 1;
					dq.emplace_back(ni, nj, nkey);
				}
			} else if ('a' <= s[ni][nj] && s[ni][nj] <= 'z') {
				if ('a' + key - 1 == s[ni][nj]) {
					if (dist[ni][nj][key] > dist[i][j][key] + 1) {
						dist[ni][nj][key] = dist[i][j][key] + 1;
						dq.emplace_back(ni, nj, key);
					}
				}
			} else {
				if (dist[ni][nj][key] > dist[i][j][key] + 1) {
					dist[ni][nj][key] = dist[i][j][key] + 1;
					dq.emplace_back(ni, nj, key);
				}
			}
		}
	}
	int ans = INF;
	for (int k = 0; k <= m; k++) {
		ans = min(ans, dist[gi][gj][k]);
	}
	if (ans == INF) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}
}
0