結果

問題 No.3121 Prime Dance
ユーザー keigo kuwata
提出日時 2025-04-24 15:52:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,039 bytes
コンパイル時間 2,621 ms
コンパイル使用メモリ 214,100 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-24 15:52:34
合計ジャッジ時間 3,881 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, Sx, Sy, Gx, Gy;
    cin >> H >> W >> Sx >> Sy >> Gx >> Gy;
    vector<string> C(H);
    for (auto &s : C) cin >> s;

    auto in = [&](int x,int y){ return 0<=x && x<H && 0<=y && y<W; };
    const int dx4[4]={1,-1,0,0}, dy4[4]={0,0,1,-1};

    /* 1) S→G の最短距離 L0 と可到達成分を求める */
    vector<vector<int>> dist(H, vector<int>(W,-1));
    queue<pair<int,int>> q;
    dist[Sx-1][Sy-1]=0; q.emplace(Sx-1,Sy-1);

    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        for(int d=0; d<4; d++){
            int nx=x+dx4[d], ny=y+dy4[d];
            if(!in(nx,ny) || C[nx][ny]=='#' || dist[nx][ny]!=-1) continue;
            dist[nx][ny]=dist[x][y]+1;
            q.emplace(nx,ny);
        }
    }
    int L0 = dist[Gx-1][Gy-1];
    if(L0==-1){ cout<<-1<<"\n"; return 0; }

    /* 2) 成分内に縦／横エッジがあるか */
    bool adjV=false, adjH=false;
    for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(dist[i][j]!=-1){
        if(i+1<H && dist[i+1][j]!=-1) adjV=true;
        if(j+1<W && dist[i][j+1]!=-1) adjH=true;
    }

    int dx = Gx-Sx,  dy = Gy-Sy;
    int dv = abs(dx), dh = abs(dy);
    if(dv==0 && !adjV){ cout<<-1<<"\n"; return 0; }
    if(dh==0 && !adjH){ cout<<-1<<"\n"; return 0; }

    /* 3) 十分大きい範囲で素数表を作る */
    const int PMAX = L0 + dv + dh + 100;      // 余裕を持たせる
    vector<char> isP(PMAX+1,1);
    isP[0]=isP[1]=0;
    for(int i=2;i*i<=PMAX;i++) if(isP[i])
        for(int j=i*i;j<=PMAX;j+=i) isP[j]=0;
    vector<int> primes; primes.reserve(PMAX/10);
    for(int i=2;i<=PMAX;i++) if(isP[i]) primes.push_back(i);
    auto prime = [&](int x){ return x>1 && x<=PMAX && isP[x]; };

    /* 4) 縦／横それぞれ「条件を満たす２素数の和」を列挙 */
    vector<int> sumV, sumH;

    if(dx>=0){
        for(int A:primes){ int B=A-dx; if(B>0 && prime(B)) sumV.push_back(A+B); }
    }else{
        for(int B:primes){ int A=B-dx; if(A>0 && prime(A)) sumV.push_back(A+B); }
    }

    if(dy>=0){
        for(int Cc:primes){ int D=Cc-dy; if(D>0 && prime(D)) sumH.push_back(Cc+D); }
    }else{
        for(int D:primes){ int Cc=D-dy; if(Cc>0 && prime(Cc)) sumH.push_back(Cc+D); }
    }

    if(sumV.empty() || sumH.empty()){ cout<<-1<<"\n"; return 0; }

    /* ループが挿入できない方向は最小値だけで十分 */
    if(!adjV) sumV = { *min_element(sumV.begin(), sumV.end()) };
    if(!adjH) sumH = { *min_element(sumH.begin(), sumH.end()) };

    sort(sumV.begin(), sumV.end());
    sort(sumH.begin(), sumH.end());

    /* 5) v+h ≥ L0 を満たす最小値を二分探索で求める */
    int ans = INT_MAX;
    for(int v : sumV){
        int need = L0 - v;
        auto it = lower_bound(sumH.begin(), sumH.end(), max(need,0));
        if(it!=sumH.end()) ans = min(ans, v + *it);
    }
    if(ans==INT_MAX) ans = -1;
    cout << ans << '\n';
    return 0;
}
0