#1103621 (C++17) No.3199 Key-Door Grid

• 問題: No.3199 Key-Door Grid
• ユーザー: 👑 potato167
• 提出日時: 2025-07-11 21:34:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 97 ms / 3,000 ms
• コード長: 5,966 bytes
• コンパイル時間: 2,146 ms
• コンパイル使用メモリ: 208,672 KB
• 実行使用メモリ: 14,464 KB
• 最終ジャッジ日時: 2025-07-11 21:35:03
• 合計ジャッジ時間: 4,350 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 37

コンパイルメッセージ

main.cpp: In function ‘void solve()’:
main.cpp:186:41: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized]
  186 |     rep(i, 0, M + 1) chmin(ans, dp[i][gx][gy]);
      |                                         ^
main.cpp:152:17: note: ‘gx’ was declared here
  152 |     int sx, sy, gx, gy;
      |                 ^~
main.cpp:186:45: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized]
  186 |     rep(i, 0, M + 1) chmin(ans, dp[i][gx][gy]);
      |                                             ^
main.cpp:152:21: note: ‘gy’ was declared here
  152 |     int sx, sy, gx, gy;
      |                     ^~
In file included from /usr/include/c++/13/bits/memory_resource.h:47,
                 from /usr/include/c++/13/string:58,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from main.cpp:1:
In constructor ‘constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(std::_Tuple_impl<_Idx, _Head, _Tail ...>&&) [with long unsigned int _Idx = 1; _Head = int; _Tail = {int}]’,
    inlined from ‘constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(std::_Tuple_impl<_Idx, _Head, _Tail ...>&&) [with long unsigned int _Idx = 0; _Head = int; _Tail = {int, int}]’ at /usr/include/c++/13/tuple:302:7,
    inlined from ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(std::tuple< <template-parameter-1-1> >&&) [with _Elements = {int, int, int}]’ at /usr/include/c++/13/tuple:903:17,
    inlined from ‘void Deque<T>::emplace_back(Args&& ...) [with Args = {std::tuple<int, int, int>}; T = std::tuple<int, int, int>]’ at main.cpp:121:9,
    inlined from ‘void Deque<T>::push_back(T&&) [with T = std::tuple<int, int, int>]’ at main.cpp:45:41,
    inlined from ‘void solve()’ at main.cpp:159:16:
/usr/include/c++/13/tuple:302:7: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
  302 |       _Tuple_imp

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}

// GPT 作
template<typename T>
struct Deque {
    Deque()
            : _cap(8), _size(0), _head(0)
    {
        _data = static_cast<T*>(operator new[](sizeof(T) * _cap));
    }

    ~Deque() {
        clear();
        operator delete[](_data);
    }

    // 要素数
    int size() const { return _size; }
    bool empty() const { return _size == 0; }

    // 前後に要素を追加
    void push_back(const T& v) { emplace_back(v); }
    void push_back(T&& v) { emplace_back(std::move(v)); }
    void push_front(const T& v) { emplace_front(v); }
    void push_front(T&& v) { emplace_front(std::move(v)); }

    // 前後から取り出し
    void pop_back() {
        assert(!empty());
        int idx = (_head + _size - 1) & (_cap - 1);
        _data[idx].~T();
        --_size;
    }
    void pop_front() {
        assert(!empty());
        _data[_head].~T();
        _head = ( _head + 1 ) & (_cap - 1);
        --_size;
    }

    // 前後の参照
    T& front() {
        assert(!empty());
        return _data[_head];
    }
    T& back() {
        assert(!empty());
        int idx = (_head + _size - 1) & (_cap - 1);
        return _data[idx];
    }

    // 添字アクセス (0 ≤ i < size())
    T& operator[](int i) {
        assert(i >= 0 && i < _size);
        return _data[( _head + i ) & (_cap - 1)];
    }
    const T& operator[](int i) const {
        assert(i >= 0 && i < _size);
        return _data[( _head + i ) & (_cap - 1)];
    }

    // 全要素をクリア
    void clear() {
        for(int i = 0; i < _size; i++){
            int idx = (_head + i) & (_cap - 1);
            _data[idx].~T();
        }
        _size = 0;
        _head = 0;
    }

private:
    T* _data;
    int _cap;   // 必ず2のべき乗
    int _size;
    int _head;  // 先頭要素のインデックス

    // 空きがなければ拡張
    void ensure_capacity() {
        if (_size < _cap) return;
        int new_cap = _cap << 1;
        T* new_data = static_cast<T*>(operator new[](sizeof(T) * new_cap));
        // 要素を head から順にコピー
        for(int i = 0; i < _size; i++){
            new (&new_data[i]) T(std::move((*this)[i]));
            (*this)[i].~T();
        }
        operator delete[](_data);
        _data = new_data;
        _cap = new_cap;
        _head = 0;
    }

    // 前後に emplace
    template<typename... Args>
    void emplace_back(Args&&... args) {
        ensure_capacity();
        int idx = (_head + _size) & (_cap - 1);
        new(&_data[idx]) T(std::forward<Args>(args)...);
        ++_size;
    }
    template<typename... Args>
    void emplace_front(Args&&... args) {
        ensure_capacity();
        _head = (_head - 1) & (_cap - 1);
        new(&_data[_head]) T(std::forward<Args>(args)...);
        ++_size;
    }
};




void solve();
// POP'N ROLL MUSIC / TOMOO
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
    int H, W, M;
    cin >> H >> W >> M;
    vector<string> S(H);
    rep(i, 0, H) cin >> S[i];
    int sx, sy, gx, gy;
    rep(i, 0, H) rep(j, 0, W){
        if (S[i][j] == 'S') sx = i, sy = j;
        if (S[i][j] == 'G') gx = i, gy = j;
    }
    vector dp(M + 1, vector(H, vector<int>(W, INF)));
    Deque<tuple<int, int, int>> q;
    q.push_back({0, sx, sy});
    dp[0][sx][sy] = 0;
    vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
    while (!q.empty()){
        auto [c, x, y] = q.front();
        q.pop_front();
        if ('1' <= S[x][y] && S[x][y] <= '9' && S[x][y] != (char)('0' + c)){
            int d = S[x][y] - '0';
            if (dp[d][x][y] == INF){
                dp[d][x][y] = dp[c][x][y];
                q.push_front({d, x, y});
            }
            continue;
        }
        if ('a' <= S[x][y] && S[x][y] <= 'z' && S[x][y] != (char)('a' + c - 1)) continue;
        rep(k, 0, 4){
            int s = dx[k] + x;
            int t = dy[k] + y;
            if (s < 0 || H <= s || t < 0 || W <= t) continue;
            if (S[s][t] == '#') continue;
            if (chmin(dp[c][s][t], dp[c][x][y] + 1)){
                q.push_back({c, s, t});
                continue;
            }
        }
    }
    int ans = INF;
    rep(i, 0, M + 1) chmin(ans, dp[i][gx][gy]);
    if (ans == INF) ans = -1;
    cout << ans << "\n";
}