結果

問題 No.3199 Key-Door Grid
ユーザー takoyaki782
提出日時 2025-07-14 20:58:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,810 bytes
コンパイル時間 4,446 ms
コンパイル使用メモリ 260,212 KB
実行使用メモリ 239,144 KB
最終ジャッジ日時 2025-07-14 20:58:25
合計ジャッジ時間 9,310 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:50:9: warning: ‘a’ may be used uninitialized [-Wmaybe-uninitialized]
   50 |     x.x = a;
      |     ~~~~^~~
main.cpp:32:9: note: ‘a’ was declared here
   32 |     int a, b, c, d;
      |         ^
main.cpp:51:9: warning: ‘b’ may be used uninitialized [-Wmaybe-uninitialized]
   51 |     x.y = b;
      |     ~~~~^~~
main.cpp:32:12: note: ‘b’ was declared here
   32 |     int a, b, c, d;
      |            ^
main.cpp:96:23: warning: ‘c’ may be used uninitialized [-Wmaybe-uninitialized]
   96 |         chmin(ans, A[c][d][i]);
      |                       ^
main.cpp:32:15: note: ‘c’ was declared here
   32 |     int a, b, c, d;
      |               ^
main.cpp:96:26: warning: ‘d’ may be used uninitialized [-Wmaybe-uninitialized]
   96 |         chmin(ans, A[c][d][i]);
      |                          ^
main.cpp:32:18: note: ‘d’ was declared here
   32 |     int 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;
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