結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー alcea
提出日時 2025-07-11 21:42:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 134 ms / 3,000 ms
コード長 1,208 bytes
コンパイル時間 2,313 ms
コンパイル使用メモリ 206,772 KB
実行使用メモリ 21,760 KB
最終ジャッジ日時 2025-07-11 21:42:53
合計ジャッジ時間 5,463 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:49:32: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized]
   49 |   for(int i=0;i<=m;i++) if(d[gi][gj][i]!=-1) ans=min(ans,d[gi][gj][i]);
      |                                ^
main.cpp:9:13: note: ‘gi’ was declared here
    9 |   int si,sj,gi,gj;
      |             ^~
main.cpp:49:36: warning: ‘gj’ may be used uninitialized [-Wmaybe-uninitialized]
   49 |   for(int i=0;i<=m;i++) if(d[gi][gj][i]!=-1) ans=min(ans,d[gi][gj][i]);
      |                                    ^
main.cpp:9:16: note: ‘gj’ was declared here
    9 |   int si,sj,gi,gj;
      |                ^~
main.cpp:20:7: warning: ‘si’ may be used uninitialized [-Wmaybe-uninitialized]
   20 |   d[si][sj][0]=0;
      |       ^
main.cpp:9:7: note: ‘si’ was declared here
    9 |   int si,sj,gi,gj;
      |       ^~
main.cpp:20:11: warning: ‘sj’ may be used uninitialized [-Wmaybe-uninitialized]
   20 |   d[si][sj][0]=0;
      |           ^
main.cpp:9:10: note: ‘sj’ was declared here
    9 |   int si,sj,gi,gj;
      |          ^~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w,m;
  cin>>h>>w>>m;
  string s[h];
  for(int i=0;i<h;i++) cin>>s[i];
  vector<vector<vector<int>>> d(h,vector<vector<int>>(w,vector<int>(m+1,-1)));
  int si,sj,gi,gj;
  for(int i=0;i<h;i++) for(int j=0;j<w;j++){
    if(s[i][j]=='S'){
      si=i;
      sj=j;
    }
    if(s[i][j]=='G'){
      gi=i;
      gj=j;
    }
  }
  d[si][sj][0]=0;
  queue<tuple<int,int,int>> Q;
  Q.push({si,sj,0});
  int dx[]{1,0,-1,0},dy[]{0,1,0,-1};
  while(!Q.empty()){
    auto [i,j,k]=Q.front();
    Q.pop();
    for(int l=0;l<4;l++){
      int ni=i+dx[l],nj=j+dy[l];
      if(ni<0||ni>=h||nj<0||nj>=w) continue;
      if(s[ni][nj]=='#') continue;
      int nk=k;
      if('1'<=s[ni][nj]&&s[ni][nj]<='9'){
        nk=s[ni][nj]-'0';
      }
      if(d[ni][nj][nk]!=-1) continue;
      if('a'<=s[ni][nj]&&s[ni][nj]<='i'){
        if(s[ni][nj]-'a'+1==nk){
          d[ni][nj][nk]=d[i][j][k]+1;
          Q.push({ni,nj,nk});
        }
      }
      else{
        d[ni][nj][nk]=d[i][j][k]+1;
        Q.push({ni,nj,nk});
      }
    }
  }
  int ans=2e9;
  for(int i=0;i<=m;i++) if(d[gi][gj][i]!=-1) ans=min(ans,d[gi][gj][i]);
  if(ans>1e9) ans=-1;
  cout<<ans<<endl;
}
0