結果

問題 No.3199 Key-Door Grid
ユーザー Rumain831
提出日時 2025-07-11 23:34:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 177 ms / 3,000 ms
コード長 1,738 bytes
コンパイル時間 1,046 ms
コンパイル使用メモリ 93,404 KB
実行使用メモリ 21,760 KB
最終ジャッジ日時 2025-07-11 23:34:42
合計ジャッジ時間 5,091 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:37: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized]
   61 |   for(int i=0; i<=m; i++) if(seen[gi][gj][i]>=0) ans=min(ans, seen[gi][gj][i]);
      |                                     ^
main.cpp:14:15: note: ‘gi’ was declared here
   14 |   int si, sj, gi, gj;
      |               ^~
main.cpp:61:41: warning: ‘gj’ may be used uninitialized [-Wmaybe-uninitialized]
   61 |   for(int i=0; i<=m; i++) if(seen[gi][gj][i]>=0) ans=min(ans, seen[gi][gj][i]);
      |                                         ^
main.cpp:14:19: note: ‘gj’ was declared here
   14 |   int si, sj, gi, gj;
      |                   ^~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<tuple>
#include<queue>
#include<algorithm>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using tu = tuple<int, int, int, int>;

int main(){
  int h, w, m; cin >> h >> w >> m;
  vector<string> s(h);
  int si, sj, gi, gj;
  for(int i=0; i<h; i++){
    cin >> s[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;
    }
  }
  vector seen(h, vector<vector<int>>(w, vector<int>(m+1, -1)));
  queue<tu> bfs;
  bfs.emplace(si, sj, 0, m);
  int di[4]={-1, 0, 1, 0};
  int dj[4]={0, 1, 0, -1};
  while(bfs.size()){
    auto [i, j, cnt, key]=bfs.front(); bfs.pop();
    //cout << "? " << i << ' ' << j << ' ' << cnt << ' ' << key << endl;
    if(seen[i][j][key]!=-1) continue;
    seen[i][j][key]=cnt;
    for(int k=0; k<4; k++){
      int ni=i+di[k], nj=j+dj[k];
      if(ni<0||nj<0||ni>=h||nj>=w) continue;
      if(s[ni][nj]=='#') continue;
      //cout << "?? " << ni << ' ' << nj << ' ' << k << ' ' << s[ni][nj] << endl;
      char now=s[ni][nj];
      if(now=='.'||now=='S'||now=='G'){
        //cout << "?" << endl;
        if(seen[ni][nj][key]==-1){
          bfs.emplace(ni, nj, cnt+1, key);
          continue;
        }
        else continue;
      }
      if(now-'1'>=0&&now-'1'<m){
        if(seen[ni][nj][now-'1'==-1]){
          bfs.emplace(ni, nj, cnt+1, now-'1');
        }
      }
      else{
        if(now-'a'==key){
          if(seen[ni][nj][key]==-1){
            bfs.emplace(ni, nj, cnt+1, key);
          }
        }
      }
    }
  }
  int ans=1e8;
  for(int i=0; i<=m; i++) if(seen[gi][gj][i]>=0) ans=min(ans, seen[gi][gj][i]);
  if(ans==1e8) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}
0