結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー ルビサファせだい
提出日時 2025-07-11 22:39:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 3,000 ms
コード長 2,640 bytes
コンパイル時間 1,438 ms
コンパイル使用メモリ 150,520 KB
実行使用メモリ 25,472 KB
最終ジャッジ日時 2025-07-11 22:39:50
合計ジャッジ時間 4,812 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath>
#include <memory>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <bitset>
#include <string>
#include <list>
#include <deque>
#include <stack>
#include <limits>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>

// #include <atcoder/fenwicktree.hpp>
#include <atcoder/segtree.hpp>
// #include <atcoder/modint.hpp>
#include <atcoder/dsu.hpp>

using namespace atcoder;
using namespace std;
using ll = long long;
using ull = unsigned long long;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;
ll ll_min = numeric_limits<ll>::min();
ll ll_max = numeric_limits<ll>::max();
ll ALPHABET_N = 26;
static const ll INF = ll_min / 10;
// using mint = modint1000000007;
#define rep(i, n) for (ll i = (ll)0; i < (ll)n; i++)
#define rep_(i, k, n) for (ll i = (ll)k; i < (ll)n; i++)
#define all(a) a.begin(), a.end()

int main()
{
	ll h, w, m;
	cin >> h >> w >> m;
	vector<string> grid(h);
	rep(i, h)
	{
		cin >> grid[i];
	}
	vector<vector<vector<ll>>> dist(10, vector<vector<ll>>(h, vector<ll>(w, ll_max)));
	ll si = 0, sj = 0, gi = 0, gj = 0;
	rep(i, h)
	{
		rep(j, w)
		{
			if (grid[i][j] == 'S')
			{
				si = i;
				sj = j;
				grid[i][j] = '.';
			}
			else if (grid[i][j] == 'G')
			{
				gi = i;
				gj = j;
				grid[i][j] = '.';
			}
		}
	}
	// (state, i, j, cost)
	queue<tuple<ll, ll, ll, ll>> q;
	q.push({0, si, sj, 0});
	dist[0][si][sj] = 0;
	vector<ll> dx = {0, 1, 0, -1};
	vector<ll> dy = {1, 0, -1, 0};
	while (!q.empty())
	{
		auto [state, i, j, cost] = q.front();
		q.pop();
		if (i == gi && j == gj)
		{
			cout << cost << endl;
			return 0;
		}
		rep(l, 4)
		{
			ll ni = i + dx[l];
			ll nj = j + dy[l];
			if (ni < 0 || ni >= h || nj < 0 || nj >= w)
				continue;
			if (grid[ni][nj] == '#')
				continue;
			if ('0' <= grid[ni][nj] && grid[ni][nj] <= '9')
			{
				ll next_state = grid[ni][nj] - '0';
				if (dist[next_state][ni][nj] > cost + 1)
				{
					dist[next_state][ni][nj] = cost + 1;
					q.push({next_state, ni, nj, cost + 1});
				}
			}
			else if ('a' <= grid[ni][nj] && grid[ni][nj] <= 'i')
			{
				if (grid[ni][nj] - 'a' == state - 1)
				{
					if (dist[state][ni][nj] > cost + 1)
					{
						dist[state][ni][nj] = cost + 1;
						q.push({state, ni, nj, cost + 1});
					}
				}
			}
			else
			{
				if (dist[state][ni][nj] > cost + 1)
				{
					dist[state][ni][nj] = cost + 1;
					q.push({state, ni, nj, cost + 1});
				}
			}
		}
	}
	cout << -1 << endl;
	return 0;
}
0