結果

問題 No.3199 Key-Door Grid
ユーザー Leal-0
提出日時 2025-07-11 22:27:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,975 bytes
コンパイル時間 2,459 ms
コンパイル使用メモリ 209,256 KB
実行使用メモリ 817,732 KB
最終ジャッジ日時 2025-07-11 22:27:19
合計ジャッジ時間 6,004 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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<ll,ll> s;
    pair<ll,ll> 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 {
        ll i;
        ll j;
        ll keyty;
    };
    queue<node> que;
    vector<vl> dist(h,vl(w,INF));
    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) {
            ll ni=nd.i+dx[i],nj=nd.j+dy[i];
            ll 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> class segtree {
    function<t(t,t)> op;
    function<t()> e;
    ll n;
    vector<t> seg;
    ll siz=1;
    public:
        segtree(ll n,function<t(t,t)> op,function<t()> e) : n(n),op(op),e(e) {
            while(siz<n) siz*=2;
            seg = vector<t>(2*siz,e());
        }
        void set(ll ind,t val) {
            ind+=siz;
            seg[ind]=val;
            while(ind>>=1) seg[ind]=op(seg[2*ind],seg[2*ind+1]);
        }

        t one_p(ll ind) {
            return seg[ind+siz];
        }

        t prod(ll lef,ll rig) { // [l,r)
            lef+=siz,rig+=siz;
            t opl=e(),opr=e();
            for(;lef<rig;lef>>=1,rig>>=1) {
                if(lef&1) opl=op(opl,seg[lef++]);
                if(rig&1) opr=op(seg[--rig],opr);
            }
            return op(opl,opr);
        }

        template<class c> ll max_right(ll lef,c judge) {
            ll LEF=lef+siz,wid=1; //LEF=seg列上の位置,lef=配列上のindex
            t ansl=e();
            for(;lef+wid<=n;LEF>>=1,wid<<=1) if(LEF&1) {
                if(!judge(op(ansl,seg[LEF]))) break;
                ansl=op(ansl,seg[LEF++]);
                lef+=wid;
            }
            while(LEF<<=1,wid>>=1) {
                //if(wid==0) break;
                if(lef+wid<=n && judge(op(ansl,seg[LEF]))) {
                    ansl=op(ansl,seg[LEF++]);
                    lef+=wid;
                }
            }
            return lef;
        }

        template<class c> ll min_left(ll rig,c judge) {
            ll RIG=rig+siz,wid=1;
            t ansr=e();
            for(;rig-wid>=0;RIG>>=1,wid<<=1) if(RIG&1) {
                if(!judge(op(seg[RIG-1],ansr))) break;
                ansr=op(seg[--RIG],ansr);
                rig-=wid;
            }
            while(RIG<<=1,wid>>=1) {
                //if(wid==0) break;
                if(rig-wid>=0 && judge(op(seg[RIG-1],ansr))) {
                    ansr=op(seg[--RIG],ansr);
                    rig-=wid;
                }
            }
            return rig;
        }
};


vector<ll> Erasieve(ll n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false; 

    for (int i=2;i*i<=n;++i) {
        if (is_prime[i]) {
            for (int j=i*i;j<=n;j+=i) is_prime[j] = false;
        }
    }
    vector<ll> primes;
    srep(i,2,n) {
        if (is_prime[i]) primes.push_back(i);
    }

    return primes;
}

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;
}

ll modpow(ll fl, ll po, ll mode) {  // mode: 0=modなし, 1=modあり
    ll ret=1;
    if (mode) {
        while (po>0) {
            if (po&1) ret=(ret*fl)%mod;
            fl=(fl*fl)%mod;
            po>>=1;
        }
    } else {
        while (po>0) {
            if(po&1) ret*=fl;
            fl*=fl;
            po>>=1;
        }
    }
    return ret;
}
#endif
0