結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー takoyaki782
提出日時 2025-07-14 20:54:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,772 bytes
コンパイル時間 4,358 ms
コンパイル使用メモリ 262,000 KB
実行使用メモリ 532,312 KB
最終ジャッジ日時 2025-07-14 20:54:58
合計ジャッジ時間 10,317 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:49:9: warning: ‘a’ may be used uninitialized [-Wmaybe-uninitialized]
   49 |     x.x = a;
      |     ~~~~^~~
main.cpp:31:8: note: ‘a’ was declared here
   31 |     ll a, b, c, d;
      |        ^
main.cpp:50:9: warning: ‘b’ may be used uninitialized [-Wmaybe-uninitialized]
   50 |     x.y = b;
      |     ~~~~^~~
main.cpp:31:11: note: ‘b’ was declared here
   31 |     ll a, b, c, d;
      |           ^
main.cpp:95:23: warning: ‘c’ may be used uninitialized [-Wmaybe-uninitialized]
   95 |         chmin(ans, A[c][d][i]);
      |                       ^
main.cpp:31:14: note: ‘c’ was declared here
   31 |     ll a, b, c, d;
      |              ^
main.cpp:95:26: warning: ‘d’ may be used uninitialized [-Wmaybe-uninitialized]
   95 |         chmin(ans, A[c][d][i]);
      |                          ^
main.cpp:31:17: note: ‘d’ was declared here
   31 |     ll a, b, c, d;
      |                 ^

ソースコード

diff # 

#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;
#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{
    ll x;
    ll y;
    ll p;
};

int main(){
    ll H, W, M;
    cin >> H >> W >> M;
    vector<string> S(H);
    ll 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<ll>>> A(H, vector<vector<ll>>(W, vector<ll>(M+1, inf_ll)));
    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);
            }
        }
    }
    ll ans = inf_ll;
    rep(i, M+1){
        chmin(ans, A[c][d][i]);
    }
    if(ans == inf_ll) ans = -1;
    cout << ans;
}
0