結果

問題 No.3199 Key-Door Grid
ユーザー Andrew8128
提出日時 2025-07-11 21:51:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 136 ms / 3,000 ms
コード長 2,753 bytes
コンパイル時間 1,285 ms
コンパイル使用メモリ 114,748 KB
実行使用メモリ 21,760 KB
最終ジャッジ日時 2025-07-11 21:51:56
合計ジャッジ時間 4,396 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using std::cerr, std::cin, std::cout, std::endl, std::fixed, std::flush;
#include <string>
using std::stoi, std::stol, std::string, std::to_string;
#include <vector>
using std::vector;
#include <array>
using std::array;
#include <deque>
using std::deque;
#include <algorithm>
using std::clamp, std::ranges::count, std::ranges::count_if, std::ranges::fill, std::ranges::find, std::ranges::find_if, std::ranges::is_permutation;
using std::ranges::lower_bound, std::ranges::max, std::ranges::max_element, std::ranges::min, std::ranges::min_element, std::ranges::next_permutation;
using std::ranges::prev_permutation, std::ranges::reverse, std::ranges::rotate, std::ranges::sort, std::ranges::unique, std::ranges::upper_bound;
static_assert(sizeof(long) == 8);
constexpr long INF = 1'070'000'000;
int main()
{
  int H, W, M;
  cin >> H >> W >> M;
  vector<string> S(H);
  for (int i = 0; i < H; i++)
  {
    cin >> S[i];
  }

  vector<vector<vector<int>>> dp(H, vector<vector<int>>(W, vector<int>(M + 1, INF)));
  deque<array<int, 3>> q;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      if (S[i][j] == 'S')
      {
        q.push_back({i, j, 0});
        dp[i][j][0] = 0;
      }
    }
  }
  const int dy[4] = {0, 1, 0, -1};
  const int dx[4] = {1, 0, -1, 0};
  while (not q.empty())
  {
    array<int, 3> now = q.front();
    q.pop_front();
    for (int d = 0; d < 4; d++)
    {
      array<int, 3> nxt = now;
      nxt[0] += dy[d];
      nxt[1] += dx[d];
      if (not(0 <= nxt[0] && nxt[0] < H))
        continue;
      if (not(0 <= nxt[1] && nxt[1] < W))
        continue;
      if (S[nxt[0]][nxt[1]] == '#')
        continue;
      if ('a' <= S[nxt[0]][nxt[1]] && S[nxt[0]][nxt[1]] <= 'z' && now[2] != S[nxt[0]][nxt[1]] - 'a' + 1)
        continue;
      if ('1' <= S[nxt[0]][nxt[1]] && S[nxt[0]][nxt[1]] <= '9')
      {
        nxt[2] = S[nxt[0]][nxt[1]] - '0';
      }
      if (dp[nxt[0]][nxt[1]][nxt[2]] > dp[now[0]][now[1]][now[2]] + 1)
      {
        dp[nxt[0]][nxt[1]][nxt[2]] = dp[now[0]][now[1]][now[2]] + 1;
        q.push_back(nxt);
      }
    }
  }
#ifdef LOCAL
  for (int k = 0; k <= M; k++)
  {
    for (int i = 0; i < H; i++)
    {
      for (int j = 0; j < W; j++)
      {
        cout << dp[i][j][k] << "   ";
      }
      cout << '\n';
    }
    cout << '\n';
    cout << '\n';
  }
#endif
  int ans = INF;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      if (S[i][j] == 'G')
        for (int k = 0; k <= M; k++)
        {
          ans = min(ans, dp[i][j][k]);
        }
    }
  }
  if (ans == INF)
    cout << -1 << '\n';
  else
    cout << ans << '\n';
  return 0;
}
/*
  File : ~/kyopro/yukicoder/554/3199.cpp
  Date : 2025/07/11
  Time : 21:34:30
*/
0