結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー takoyaki782
提出日時 2025-07-14 20:58:16
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,810 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,969 ms
コンパイル使用メモリ 284,064 KB
実行使用メモリ 474,196 KB
最終ジャッジ日時 2026-07-13 06:02:16
合計ジャッジ時間 8,514 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/allocator.h:46,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/string:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bitset:54,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:1:
In member function 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = point; _Args = {const point&}; _Tp = point]',
    inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = point; _Args = {const point&}; _Tp = point]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/alloc_traits.h:674:17,
    inlined from 'void std::deque<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = point; _Alloc = std::allocator<point>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_deque.h:1610:30,
    inlined from 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = point; _Sequence = std::deque<point, std::allocator<point> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_queue.h:313:20,
    inlined from 'int main()' at main.cpp:53:11:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/new_allocator.h:191:11: warning: 'a' may be used uninitialized [-Wmaybe-uninitialized]
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function 'int main()':
main.cpp:32:9: note: 'a' was declared here
   32 |     int a, b, c, d;
      |         ^
In member function 'void std::__new_allocator<_Tp>::construct(

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll inf_ll = 9223372036854775807;
int inf_int = 2147483647;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using mint = atcoder::modint998244353;
using mint1 = atcoder::modint1000000007;
using Pa = std::pair<ll, ll>;

int Yes(bool x){
    if(x) cout << "Yes";
    else cout << "No";
    cout << endl;
    return 0;
}

struct point{
    int x;
    int y;
    int p;
};

int main(){
    int H, W, M;
    cin >> H >> W >> M;
    vector<string> S(H);
    int a, b, c, d;
    rep(i, H){
        cin >> S[i];
        rep(j, W){
            if(S[i][j] == 'S'){
                a = i;
                b = j;
            }
            if(S[i][j] == 'G'){
                c = i;
                d = j;
            }
        }
    }
    vector<vector<vector<int>>> A(H, vector<vector<int>>(W, vector<int>(M+1, inf_int)));
    queue<point> Q;
    A[a][b][0] = 0;
    point x;
    x.x = a;
    x.y = b;
    x.p = 0;
    Q.push(x);
    ll dx[4] = {1, -1, 0, 0};
    ll dy[4] = {0, 0, 1, -1};
    while(!Q.empty()){
        auto y = Q.front();
        Q.pop();
        rep(i, 4){
            if(y.x+dx[i]>=0 && y.x+dx[i]<H && y.y+dy[i]>=0 && y.y+dy[i]<W){
                if(S[y.x+dx[i]][y.y+dy[i]] == '#') continue;
                bool a = false;
                rep(k, M){
                    if(S[y.x+dx[i]][y.y+dy[i]] - '1' == k){
                        a = true;
                        if(A[y.x+dx[i]][y.y+dy[i]][k+1] <= A[y.x][y.y][y.p]) continue;
                        A[y.x+dx[i]][y.y+dy[i]][k+1] = A[y.x][y.y][y.p] + 1;
                        point z;
                        z.x = y.x+dx[i];
                        z.y = y.y+dy[i];
                        z.p = k+1;
                        Q.push(z);
                    }
                }
                if(a) continue;
                rep(k, M){
                    if(S[y.x+dx[i]][y.y+dy[i]] - 'a' == k){
                        if(y.p != k+1){
                            a = true;
                        }
                    }
                }
                if(a) continue;
                if(A[y.x+dx[i]][y.y+dy[i]][y.p] <= A[y.x][y.y][y.p]) continue;
                A[y.x+dx[i]][y.y+dy[i]][y.p] = A[y.x][y.y][y.p] + 1;
                point z;
                z.x = y.x+dx[i];
                z.y = y.y+dy[i];
                z.p = y.p;
                Q.push(z);
            }
        }
    }
    int ans = inf_int;
    rep(i, M+1){
        chmin(ans, A[c][d][i]);
    }
    if(ans == inf_int) ans = -1;
    cout << ans;
}
0