結果

問題 No.3199 Key-Door Grid
ユーザー Leal-0
提出日時 2025-07-11 23:20:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 89 ms / 3,000 ms
コード長 1,933 bytes
コンパイル時間 2,221 ms
コンパイル使用メモリ 208,816 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-11 23:20:56
合計ジャッジ時間 4,878 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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,goal;
    rep(i,h)rep(j,w){
        cin>>g[i][j];
        if(g[i][j]=='S') s={i,j};
        if(g[i][j]=='G') goal={i,j};
    }
    struct node{
        int i;
        int j;
        int keyty;
    };
    vector<vector<array<bool,10>>> seen(h,vector<array<bool,10>>(w));
    seen[s.first][s.second][0]=1;
    vector<node> cur,nxt;
    cur.reserve(h*w);nxt.reserve(h*w);
    cur.push_back({s.first,s.second,0});
    int depth=0;
    while(cur.size()){
        for(auto &nd : cur){
            if(nd.i==goal.first && nd.j==goal.second){
                cout<<depth<<nl;
                return 0;
            }
            rep(d,4){
                int ni=nd.i+dx[d],nj=nd.j+dy[d];
                if(!isin(ni,nj,h,w) || g[ni][nj]=='#')continue;
                int kty=nd.keyty;
                char c=g[ni][nj];
                if(c>='a'&&c<='i'){
                    int door=c-'a'+1;
                    if(door!=kty)continue;
                }
                if(c>='1'&&c<='9')kty=c-'0';
                if(!seen[ni][nj][kty]){
                    seen[ni][nj][kty]=1;
                    nxt.push_back({ni,nj,kty});
                }
            }
        }
        cur.clear();
        swap(cur,nxt);
        depth++;
    }
    cout<<-1<<nl;
    return 0;
}

/////// 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 nl "\n"
#define vl vector<ll>
#define vc vector<char>
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

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;
}
#endif
0