結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー tombo_
提出日時 2026-01-03 11:25:58
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 141 ms / 3,000 ms
コード長 3,093 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,020 ms
コンパイル使用メモリ 285,984 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2026-01-03 11:26:08
合計ジャッジ時間 8,914 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:62:10: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
   62 |   dist[sx][sy][M] = 0;
      |          ^
main.cpp:56:7: note: 'sx' was declared here
   56 |   int sx, sy, tx, ty;
      |       ^~
main.cpp:62:14: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
   62 |   dist[sx][sy][M] = 0;
      |              ^
main.cpp:56:11: note: 'sy' was declared here
   56 |   int sx, sy, tx, ty;
      |           ^~
main.cpp:93:26: warning: 'tx' may be used uninitialized [-Wmaybe-uninitialized]
   93 |   REP(i, 0, M) if(dist[tx][ty][i] != -1) chmin(ans, dist[tx][ty][i]);
      |                          ^
main.cpp:56:15: note: 'tx' was declared here
   56 |   int sx, sy, tx, ty;
      |               ^~
main.cpp:93:30: warning: 'ty' may be used uninitialized [-Wmaybe-uninitialized]
   93 |   REP(i, 0, M) if(dist[tx][ty][i] != -1) chmin(ans, dist[tx][ty][i]);
      |                              ^
main.cpp:56:19: note: 'ty' was declared here
   56 |   int sx, sy, tx, ty;
      |                   ^~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define REP(i, l, r) rep(i, l, r+1)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
struct Edge {
  int to; ll w;
};
using Graph = vector<vector<int> >;
//using Graph = vector<vector<Edge> >;
const ll INF = 2e18;
//const int INF = 2e9;
template<class T> using vc = vector<T>;
template<class T> using vv = vector<vector<T> >;
template<class T> using vvv = vector<vector<vector<T> > >;
template<class T> using pq = priority_queue<T>;
template<class T> using pq_g = priority_queue<T, vc<T>, greater<T> >;
template<class T> istream& operator>>(istream& i, vc<T>& v) { rep(j, 0, v.size()) i>>v[j]; return i; }
template<class T> ostream& operator<<(ostream& o, vc<T>& v) { rep(j, 0, v.size()) o<<v[j]<<" "; return o; }
template<class T> bool chmin(T& a, T b) {
  if(a > b) {
      a = b;
      return true;
  }
  return false;
}
template<class T> bool chmax(T& a, T b) {
  if(a < b) {
      a = b;
      return true;
  }
  return false;
}

int main() {
  // 高速化
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // 小数点の出力桁数を指定
  cout << fixed << setprecision(10);
  // メイン
  int H, W, M;
  cin >> H >> W >> M;
  vc<string> S(H);
  cin >> S;
  int sx, sy, tx, ty;
  rep(i, 0, H) rep(j, 0, W) {
      if(S[i][j]=='S') sx = i, sy = j;
      if(S[i][j]=='G') tx = i, ty = j;
  }
  vvv<int> dist(H, vv<int>(W, vc<int>(M+1, -1)));
  dist[sx][sy][M] = 0;
  queue<array<int, 3>> que;
  que.push({sx, sy, M});
  vc<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
  while(!que.empty()) {
      auto [x, y, k] = que.front(); que.pop();
      rep(i, 0, 4) {
          int nx = x+dx[i], ny = y+dy[i];
          if(0 <= nx && nx < H && 0 <= ny && ny < W && S[nx][ny]!='#') {
              if('a' <= S[nx][ny] && S[nx][ny] <= 'z') {
                  if(S[nx][ny]-'a'==k) {
                      if(dist[nx][ny][k] == -1) {
                      dist[nx][ny][k] = dist[x][y][k]+1;
                      que.push({nx, ny, k});
                      }
                  }
              } else if('1' <= S[nx][ny] && S[nx][ny] <= '9') {
                  if(dist[nx][ny][S[nx][ny]-'1'] == -1) {
                  dist[nx][ny][S[nx][ny]-'1'] = dist[x][y][k]+1;
                  que.push({nx, ny, S[nx][ny]-'1'});
                  }
              } else {
                  if(dist[nx][ny][k] == -1) {
                  dist[nx][ny][k] = dist[x][y][k]+1;
                  que.push({nx, ny, k});
                  }
              }
          }
      }
  }
  int ans = 100000000;
  REP(i, 0, M) if(dist[tx][ty][i] != -1) chmin(ans, dist[tx][ty][i]);
  if(ans != 100000000) cout<< ans << endl;
  else cout << -1 << endl;

  return 0;
}
0