結果

問題 No.3121 Prime Dance
コンテスト
ユーザー GOTKAKO
提出日時 2025-04-19 06:33:14
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 515 ms / 2,000 ms
コード長 2,930 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,991 ms
コンパイル使用メモリ 228,968 KB
実行使用メモリ 93,312 KB
最終ジャッジ日時 2025-04-19 06:33:23
合計ジャッジ時間 8,361 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    int H,W; cin >> H >> W;
    int sx = -1,sy = -1,gx = -1,gy = -1;
    cin >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;

    vector<string> S(H);
    for(auto &s : S) cin >> s;
    if(H == 1 || W == 1){cout << -1 << endl; return 0;}

    vector<pair<int,int>> dxy = {{-1,0},{0,1},{1,0},{0,-1}};
    vector<vector<vector<pair<int,int>>>> adj(H,vector<vector<pair<int,int>>>(W));
    auto Adj = [&](int x,int y) -> void {
        vector<pair<int,int>> now;
        for(auto [dx,dy] : dxy){
            int nx = dx+x,ny = dy+y;
            if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
            if(S.at(nx).at(ny) == '#') continue;
            now.emplace_back(pair{nx,ny});
        }
        adj.at(x).at(y) = now;
    };
    for(int i=0; i<H; i++) for(int k=0; k<W; k++) Adj(i,k);

    vector dist(H,vector(W,vector(1001,vector(4,-1))));
    deque<tuple<int,int,int,int>> Q;    
    dist[sx][sy][0][0] = 0; Q.push_front({sx,sy,0,0});

    while(Q.size()){
        auto [x,y,A,ok] = Q.front(); Q.pop_front();
        if(A == 1000) continue; //あやしい.
        int d = dist.at(x).at(y).at(A).at(ok);
        for(auto [nx,ny] : adj.at(x).at(y)){
            if(x == nx) ok |= 2;
            else ok |= 1;
        }
        if(dist.at(x).at(y).at(A).at(ok) != d && dist.at(x).at(y).at(A).at(ok) != -1) continue;
        dist.at(x).at(y).at(A).at(ok) = d;

        for(auto [nx,ny] : adj.at(x).at(y)){
            if(x == nx && y+1 == ny) d++;
            else if(x+1 == nx && y == ny) A++;
            if(dist.at(nx).at(ny).at(A).at(ok) == -1){
                dist.at(nx).at(ny).at(A).at(ok) = d;
                if(x == nx && y+1 == ny) Q.emplace_back(tuple{nx,ny,A,ok});
                else Q.emplace_front(tuple{nx,ny,A,ok});
            }
            if(x == nx && y+1 == ny) d--;
            else if(x+1 == nx && y == ny) A--;
        }
    }

    int Need = 1001001;
    vector<bool> prime(Need+1,true);
    prime.at(0) = false; prime.at(1) = false;
    for(int i=2; i*i<=Need; i++){
        if(!prime.at(i)) continue;
        for(int k=i*i; k<=Need; k+=i) prime.at(k) = false;
    }

    int answer = 1001001001,dx = gx-sx,dy = gy-sy;
    for(int a=0; a<1000; a++){
        int A = a;
        int C = dist.at(gx).at(gy).at(A).at(3);
        if(C == -1) continue;
        int B = A-dx,D = C-dy;
        bool ok = false;
        for(int i=0; i<=1000; i++){
            if(prime.at(A) && prime.at(B)){ok = true; break;}
            A++; B++;
        }
        if(!ok) continue;
        ok = false;
        for(int i=0; i<=1000; i++){
            if(prime.at(C) && prime.at(D)){ok = true; break;}
            C++; D++;
        }
        if(!ok) continue;
        int now = A+B+C+D;
        answer = min(answer,now);
    }
    if(answer > 1e9) answer = -1;
    cout << answer << endl;
}
0