結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー tanaka255
提出日時 2025-07-13 14:04:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 119 ms / 3,000 ms
コード長 1,326 bytes
コンパイル時間 3,920 ms
コンパイル使用メモリ 284,308 KB
実行使用メモリ 13,664 KB
最終ジャッジ日時 2025-07-13 14:04:46
合計ジャッジ時間 6,729 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
int H,W,M;
string S[500];
int dp[10][500][500];
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>H>>W>>M;
  rep(i,H)cin>>S[i];
  int sx=-1,sy=-1,tx=-1,ty=-1;
  rep(i,H)rep(j,W){
    if(S[i][j]=='S'){
      sx=i,sy=j;
      S[i][j]='.';
    }
    if(S[i][j]=='G'){
      tx=i,ty=j;
      S[i][j]='.';
    }
  }
  constexpr int inf=1<<30;
  rep(k,M+1)rep(i,H)rep(j,W)dp[k][i][j]=inf;
  dp[0][sx][sy]=0;
  queue<tuple<int,int,int>>que;
  que.push({0,sx,sy});
  while(!que.empty()){
    auto[k,x,y]=que.front();
    que.pop();
    int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
    rep(dir,4){
      int xx=x+dx[dir],yy=y+dy[dir];
      if(!(0<=xx&&xx<H&&0<=yy&&yy<W))continue;
      if(S[xx][yy]=='#')continue;
      if(S[xx][yy]=='.'&&dp[k][xx][yy]==inf){
        dp[k][xx][yy]=dp[k][x][y]+1;
        que.push({k,xx,yy});
      }
      if('1'<=S[xx][yy]&&S[xx][yy]<='9'&&dp[S[xx][yy]-'0'][xx][yy]==inf){
        dp[S[xx][yy]-'0'][xx][yy]=dp[k][x][y]+1;
        que.push({S[xx][yy]-'0',xx,yy});
      }
      if(1<=k&&S[xx][yy]=='a'+(k-1)&&dp[k][xx][yy]==inf){
        dp[k][xx][yy]=dp[k][x][y]+1;
        que.push({k,xx,yy});
      }
    }
  }
  int ans=inf;
  rep(k,M+1)ans=min(ans,dp[k][tx][ty]);
  if(ans==inf)ans=-1;
  cout<<ans<<endl;
}
0