結果

問題 No.3121 Prime Dance
ユーザー Yu_212
提出日時 2025-04-19 11:04:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 5,735 bytes
コンパイル時間 3,590 ms
コンパイル使用メモリ 292,596 KB
実行使用メモリ 23,808 KB
最終ジャッジ日時 2025-04-19 11:05:04
合計ジャッジ時間 5,193 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int iinf = 1e9;
const ll inf = 1e18;
template<ll mod>
struct Mint {
    using M=Mint; ll v;
    M& put(ll x) { v=(x<mod)?x:x-mod; return *this; }
    Mint(ll x=0) { put(x%mod+mod); }
    M operator+(M m) {return M().put(v+m.v);}
    M operator-(M m) {return M().put(v+mod-m.v);}
    M operator*(M m) {return M().put(v*m.v%mod);}
    M operator/(M m) {return M().put(v*m.inv().v%mod);}
    M operator+=(M m) { return put(v+m.v); }
    M operator-=(M m) { return put(v+mod-m.v); }
    M operator*=(M m) { return put(v*m.v%mod); }
    M operator/=(M m) { return put(v*m.inv().v%mod); }
    bool operator==(M m) { return v==m.v; }
    M pow(ll m) const {
        M x=v, res=1;
        while (m) {
            if (m&1) res=res*x;
            x=x*x; m>>=1;
        }
        return res;
    }
    M inv() { return pow(mod-2); }
};
template<ll mod>
ostream&operator<<(ostream&o,Mint<mod>v){return o<<v.v;}


template<typename T>
ostream& operator<<(ostream &o, vector<T> v) {
    for (int i = 0; i < v.size(); i++)
        o << v[i] << (i+1<v.size()?" ":"");
    return o;
}
template <typename T>
struct SegTree {
    using F = function<T(T, T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegTree() {}
    SegTree(F f, T ti,int num) : f(f), ti(ti) {
        n = max(__bit_ceil(num), 1);
        dat.assign(n << 1, ti);
    }
    SegTree(F f,T ti,vector<T>&v):SegTree(f,ti,v.size()){
        for (int i = 0; i < v.size(); i++)
            dat[n + i] = v[i];
        for(int i=n-1;i;i--) dat[i]=f(dat[i*2], dat[i*2+1]);
    }
    void set_val(int k, T x) {
        dat[k += n] = x;
        while(k >>= 1) dat[k] = f(dat[k*2], dat[k*2+1]);
    }
    T query(int a, int b) {
        if (a >= b) return ti;
        T vl = ti, vr = ti;
        for (int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
            if (l & 1) vl = f(vl, dat[l++]);
            if (r & 1) vr = f(dat[--r], vr);
        }
        return f(vl, vr);
    }
};
struct Edge { int to; ll cost; };

const int MOD = 998244353;

// a^e mod
ll modpow(ll a, ll e=MOD-2){
    ll r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return r;
}

using mint = Mint<MOD>;
using i128 = __int128_t;
using ull = unsigned long long;
i128 pow128(i128 a,ull d,ull m){//remove m,i128->mint64
    i128 res=1;
    while (d) { if (d&1) (res*=a)%=m; (a*=a)%=m; d>>=1; }
    return res;
}
bool is_prime(ull n) {
    if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
    //  mint64::set_mod(n);
    // {2,7,61,-1} -> n < 4759123141 (= 2^32)
    int test[] = {2,3,5,7,11,13,17,19,23,-1}; // n<1e16
    ull d = n - 1, s = 0;
    while (d % 2 == 0) ++s, d /= 2;
    for (int i = 0; test[i] < n && test[i] != -1; i++) {
        auto x = pow128(test[i], d, n);
        if (x == 1) goto end;
        for (int r = 0; r < s; r++) {
            if (x == n - 1) goto end;
            (x *= x) %= n;
        }
        return false;
        end:;
    }
    return true;
}


int main() {
    cin.tie(0)->sync_with_stdio(false);


    int H, W;
    cin >> H >> W;
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    // 1-indexed -> 0-index
    sx--; sy--; gx--; gy--;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }

    int maxMoves = H * W;
    vector dist(H,vector(W,vector<array<int,2>>(maxMoves+1, {iinf, iinf})));

    struct State { int x, y, h, usedV; };
    deque<State> q;

    dist[sx][sy][0][0] = 0;
    q.push_back({sx, sy, 0, 0});

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        State cur = q.front(); q.pop_front();
        int x = cur.x, y = cur.y, h = cur.h, usedV = cur.usedV;
        int d = dist[x][y][h][usedV];
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (grid[nx][ny] == '#') continue;
            int nh = h + (k >= 2);
            int nUsedV = usedV || (k < 2);
            if (nh > maxMoves) continue;
            int nd = d + 1;
            if (nd < dist[nx][ny][nh][nUsedV]) {
                dist[nx][ny][nh][nUsedV] = nd;
                q.push_back({nx, ny, nh, nUsedV});
            }
        }
    }

    int dv = abs(sx - gx);
    int dh = abs(sy - gy);
    int ans = iinf;
    vector<int> oksv;
    vector<int> oksh;
    if (dv % 2 == 1) {
        if (is_prime(2+dv)) oksv.push_back(2);
    } else {
        if (dv == 0) oksv.push_back(2);
        for (int i = 3; ; i += 2) {
            if (is_prime(i) and is_prime(i+dv)) {
                oksv.push_back(i);
                if (i > maxMoves) break;
            }
        }
    }
    if (dh % 2 == 1) {
        if (is_prime(2+dh)) oksh.push_back(2);
    } else {
        if (dh == 0) oksh.push_back(2);
        for (int i = 3; ; i += 2) {
            if (is_prime(i) and is_prime(i+dh)) {
                oksh.push_back(i);
                if (i > maxMoves) break;
            }
        }
    }
    // cout << dv << " " << dh << endl;
    for (int i = 1; i <= maxMoves; i++) {
        if (dist[gx][gy][i][1] >= iinf) continue;
        int j = dist[gx][gy][i][1]-i;

        int mv = (j-dv)/2;
        int mh = (i-dh)/2;
        auto itv = lower_bound(oksv.begin(), oksv.end(), mv);
        auto ith = lower_bound(oksh.begin(), oksh.end(), mh);
        if (itv != oksv.end() && ith != oksh.end()) {
            // cout << i << " " << j << " " << mv << " " << mh << endl;
            mv = *itv;
            mh = *ith;
            // cout << mv << " " << mh << endl;
            ans = min(ans, mv + mv+dv + mh + mh+dh);
        }
    }
    cout << (ans==iinf?-1:ans) << endl;

    return 0;
}
0