結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー otoshigo
提出日時 2025-07-11 22:43:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 126 ms / 3,000 ms
コード長 2,161 bytes
コンパイル時間 3,756 ms
コンパイル使用メモリ 291,532 KB
実行使用メモリ 21,504 KB
最終ジャッジ日時 2025-07-11 22:43:19
合計ジャッジ時間 6,365 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:40:12: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
   40 |     dist[sx][sy][0]=0;
      |            ^
main.cpp:30:9: note: ‘sx’ was declared here
   30 |     int sx,sy;
      |         ^~
main.cpp:40:16: warning: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized]
   40 |     dist[sx][sy][0]=0;
      |                ^
main.cpp:30:12: note: ‘sy’ was declared here
   30 |     int sx,sy;
      |            ^~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for(ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

#define TT template<typename T>
TT using vec = vector<T>;
template<class T1, class T2> bool chmin(T1 &x, T2 y) { return x > y ? (x = y, true) : false; }
template<class T1, class T2> bool chmax(T1 &x, T2 y) { return x < y ? (x = y, true) : false; }

struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int INF=1<<30;

void solve(){
    int H,W,M;
    cin>>H>>W>>M;
    vector<string>S(H);
    rep(i,0,H)cin>>S[i];
    int sx,sy;
    rep(i,0,H){
        rep(j,0,W){
            if(S[i][j]=='S'){
                sx=i;
                sy=j;
            }
        }
    }
    vector dist(H,vector(W,vector<int>(M+1,INF)));
    dist[sx][sy][0]=0;
    deque<tuple<int,int,int,int>>dq;
    dq.push_back({dist[sx][sy][0],sx,sy,0});
    while(dq.size()){
        auto[cost,x,y,t]=dq.front();
        dq.pop_front();
        if(S[x][y]=='G'){
            cout<<cost<<"\n";
            return;
        }
        if(dist[x][y][t]<cost)continue;
        if('1'<=S[x][y]&&S[x][y]<='9'){
            if(chmin(dist[x][y][S[x][y]-'0'],cost)){
                dq.push_front({dist[x][y][S[x][y]-'0'],x,y,S[x][y]-'0'});
            }
            if(S[x][y]-'0'!=t)continue;
        }
        rep(i,0,4){
            int ex=x+dx[i],ey=y+dy[i];
            if(!(0<=ex&&ex<H&&0<=ey&&ey<W))continue;
            if(S[ex][ey]=='#')continue;
            if('a'<=S[ex][ey]&&S[ex][ey]<='i'){
                if(S[ex][ey]-'a'+1==t&&chmin(dist[ex][ey][t],cost+1)){
                    dq.push_back({dist[ex][ey][t],ex,ey,t});
                }
            }else{
                if(chmin(dist[ex][ey][t],cost+1)){
                    dq.push_back({dist[ex][ey][t],ex,ey,t});
                }
            }
        }
    }
    cout<<-1<<"\n";
}

int main() {
    solve();
}
0