結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー Leal-0
提出日時 2025-07-11 22:43:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,233 bytes
コンパイル時間 2,255 ms
コンパイル使用メモリ 208,840 KB
実行使用メモリ 814,656 KB
最終ジャッジ日時 2025-07-11 22:43:50
合計ジャッジ時間 7,045 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__
int main(void) {
    ll h,w,m; cin>>h>>w>>m;
    vector<vc> g(h,vc(w));
    pair<int,int> s;
    pair<int,int> goal;
    rep(i,h) rep(j,w) {
        cin>>g[i][j];
        if(g[i][j]=='S') s=make_pair(i,j);
        if(g[i][j]=='G') goal=make_pair(i,j);
    }
    struct node {
        int i;
        int j;
        int keyty;
    };
    queue<node> que;
    vector<vector<int>> dist(h,vector<int>(w,1e9));
    dist[s.first][s.second]=0;
    que.push({s.first,s.second,-1});
    while(!que.empty()) {
        node nd=que.front();
        que.pop();
        rep(i,4) {
            int ni=nd.i+dx[i],nj=nd.j+dy[i];
            int kty=nd.keyty;
            if(!isin(ni,nj,h,w)) continue;
            if(g[ni][nj]=='#') continue;
            if(g[ni][nj]>='a' && g[ni][nj]<='i' && g[ni][nj]!=char('a'+nd.keyty-1)) continue;
            if(dist[ni][nj]<=dist[nd.i][nd.j]) continue;
            dist[ni][nj]=dist[nd.i][nd.j]+1;
            if(g[ni][nj]=='G') {
                cout<<dist[ni][nj]<<nl;
                return 0;
            }
            if(g[ni][nj]>='1' && g[ni][nj]<='9') kty=g[ni][nj]-'0';
            que.push({ni,nj,kty});
        }
    }
    cout<<-1<<nl;
}

/////// library zone ///////
#else
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define srep(i,l,r) for(ll i=l;i<=r;i++)
#define irep(i,r,l) for(ll i=r;i>=l;i--)
using ll = long long;
using ld = long double;
const ll mod=998244353;
#define vout(v) for(auto i :v) cout<<i<<" ";
#define INF 9223300000000000000ll
#define Winf 5e12
#define nl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vl vector<ll>
#define vc vector<char>
#define pb push_back

vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
bool isin(ll i,ll j,ll h,ll w) {
    return (i>=0 && i<h && j>=0 && j<w);
}
ll op(ll a,ll b) {return max(a,b);}
ll e() {return -Winf; }


template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}

void no() { cout<<"No"<<nl;}
void yes() { cout<<"Yes"<<nl;}
void yn(bool a) {
    cout<<(a ? "Yes":"No")<<nl;
}

#endif
0