結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー tau1235
提出日時 2025-07-11 21:45:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 128 ms / 3,000 ms
コード長 1,076 bytes
コンパイル時間 3,446 ms
コンパイル使用メモリ 293,056 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2025-07-11 21:45:45
合計ジャッジ時間 6,186 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:43:49: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized]
   43 |   for (int i=0;i<=m;i++) ans=min(ans,dist[gy][gx][i]);
      |                                                 ^
main.cpp:10:13: note: ‘gx’ was declared here
   10 |   int sx,sy,gx,gy;
      |             ^~
main.cpp:43:45: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized]
   43 |   for (int i=0;i<=m;i++) ans=min(ans,dist[gy][gx][i]);
      |                                             ^
main.cpp:10:16: note: ‘gy’ was declared here
   10 |   int sx,sy,gx,gy;
      |                ^~
main.cpp:20:14: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
   20 |   dist[sy][sx][0]=0;
      |              ^
main.cpp:10:7: note: ‘sx’ was declared here
   10 |   int sx,sy,gx,gy;
      |       ^~
main.cpp:20:10: warning: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized]
   20 |   dist[sy][sx][0]=0;
      |          ^
main.cpp:10:10: note: ‘sy’ was declared here
   10 |   int sx,sy,gx,gy;
      |          ^~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

int main(){
  int inf=2e9;
  vector<int> dy={1,0,-1,0},dx={0,1,0,-1};
  int h,w,m;
  cin>>h>>w>>m;
  vector<string> s(h);
  int sx,sy,gx,gy;
  for (int i=0;i<h;i++){
    cin>>s[i];
    for (int j=0;j<w;j++){
      char c=s[i][j];
      if (c=='S') sy=i,sx=j;
      if (c=='G') gy=i,gx=j;
    }
  }
  vector dist(h,vector(w,vector<int>(m+1,inf)));
  dist[sy][sx][0]=0;
  queue<tuple<int,int,int>> q;
  q.push({sy,sx,0});
  while (!q.empty()){
    auto [i,j,k]=q.front();
    q.pop();
    for (int d=0;d<4;d++){
      int ny=i+dy[d],nx=j+dx[d];
      int nk=k;
      if (!(0<=ny&&ny<h&&0<=nx&&nx<w)) continue;
      char c=s[ny][nx];
      if (c=='#') continue;
      if ('1'<=c&&c<='9') nk=c-'0';
      if ('a'<=c&&c<='i'){
        int k2=c-'a'+1;
        if (k!=k2) continue;
      }
      if (dist[ny][nx][nk]!=inf) continue;
      dist[ny][nx][nk]=dist[i][j][k]+1;
      q.push({ny,nx,nk});
    }
  }
  int ans=inf;
  for (int i=0;i<=m;i++) ans=min(ans,dist[gy][gx][i]);
  if (ans==inf) cout<<-1<<endl;
  else cout<<ans<<endl;
}
0