結果

問題 No.3121 Prime Dance
ユーザー hirayuu_yc
提出日時 2025-04-19 13:30:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 642 ms / 2,000 ms
コード長 5,480 bytes
コンパイル時間 3,899 ms
コンパイル使用メモリ 307,864 KB
実行使用メモリ 206,720 KB
最終ジャッジ日時 2025-04-19 13:31:00
合計ジャッジ時間 10,994 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
from collections import deque
from bisect import bisect_left
H,W=map(int,input().split())
sx,sy=map(int,input().split())
gx,gy=map(int,input().split())
S=["#"*(W+2) for i in range(H+2)]
for i in range(H):
    S[i+1]="#"+input()+"#"
S=[list(s) for s in S]
S[sx][sy]="."
S[gx][gy]="."
H+=2
W+=2
num=[[0]*W for i in range(H)]
for i in range(1,H-1):
    for j in range(1,W-1):
        if S[i-1][j]=="." or S[i+1][j]==".":
            num[i][j]^=1
        if S[i][j-1]=="." or S[i][j+1]==".":
            num[i][j]^=2
dist=[[[[1<<60]*4 for i in range(1600)] for i in range(W)] for i in range(H)]
dist[sx][sy][0][num[sx][sy]]=0
vert=deque()
vert.append((0,sx,sy,0,num[sx][sy]))
while vert:
    d,x,y,r,b=vert.popleft()
    if dist[x][y][r][b]!=d:
        continue
    if S[x+1][y]==".":
        if dist[x+1][y][r][b|num[x+1][y]]>d+1:
            dist[x+1][y][r][b|num[x+1][y]]=d+1
            vert.append((d+1,x+1,y,r,b|num[x+1][y]))
    if S[x-1][y]==".":
        if dist[x-1][y][r][b|num[x-1][y]]>d:
            dist[x-1][y][r][b|num[x-1][y]]=d
            vert.appendleft((d,x-1,y,r,b|num[x-1][y]))
    if S[x][y+1]==".":
        if r!=1599 and dist[x][y+1][r+1][b|num[x][y+1]]>d:
            dist[x][y+1][r+1][b|num[x][y+1]]=d
            vert.appendleft((d,x,y+1,r+1,b|num[x][y+1]))
    if S[x][y-1]==".":
        if dist[x][y-1][r][b|num[x][y-1]]>d:
            dist[x][y-1][r][b|num[x][y-1]]=d
            vert.appendleft((d,x,y-1,r,b|num[x][y-1]))
swx=gx-sx
swy=gy-sy
X=30000
primes=[1]*X
primes[0]=0
primes[1]=0
for i in range(2,X):
    if primes[i]==0:
        continue
    for j in range(i*2,X,i):
        primes[j]=0
px=[]
py=[]
for i in range(X):
    if 0<=i-swx<X and primes[i] and primes[i-swx]:
        px.append(i)
for i in range(X):
    if 0<=i-swy<X and primes[i] and primes[i-swy]:
        py.append(i)
px.append(1<<60)
py.append(1<<60)
ans=1<<60
for i in range(1600):
    ans=min(ans,(px[bisect_left(px,dist[gx][gy][i][3])]+py[bisect_left(py,i)])*2-swx-swy)
if ans>=(1<<60):
    print(-1)
else:
    print(ans)
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

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

    int H0, W0;
    cin >> H0 >> W0;
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;

    int H = H0 + 2, W = W0 + 2;
    vector<string> S(H, string(W, '#'));
    for(int i = 0; i < H0; i++){
        string row;
        cin >> row;
        S[i+1] = "#" + row + "#";
    }
    // mark start/goal walkable
    S[sx][sy] = '.';
    S[gx][gy] = '.';

    // compute bitmask of open neighbors
    vector<vector<int>> num(H, vector<int>(W, 0));
    for(int i = 1; i < H-1; i++){
        for(int j = 1; j < W-1; j++){
            if(S[i-1][j]=='.' || S[i+1][j]=='.') num[i][j] ^= 1;
            if(S[i][j-1]=='.' || S[i][j+1]=='.') num[i][j] ^= 2;
        }
    }

    // dist[x][y][r][b] = minimal cost
    vector<vector<vector<vector<ll>>>> dist(
        H, vector<vector<vector<ll>>>(
            W, vector<vector<ll>>(
                1600, vector<ll>(4, INF)
            )
        )
    );
    dist[sx][sy][0][ num[sx][sy] ] = 0;

    deque< tuple<ll,int,int,int,int> > dq;
    dq.emplace_back(0, sx, sy, 0, num[sx][sy]);

    while(!dq.empty()){
        auto [d,x,y,r,b] = dq.front(); dq.pop_front();
        if(dist[x][y][r][b] != d) continue;
        // move down (cost+1)
        if(S[x+1][y]=='.'){
            int nb = b | num[x+1][y];
            if(dist[x+1][y][r][nb] > d+1){
                dist[x+1][y][r][nb] = d+1;
                dq.emplace_back(d+1, x+1, y, r, nb);
            }
        }
        // move up (cost)
        if(S[x-1][y]=='.'){
            int nb = b | num[x-1][y];
            if(dist[x-1][y][r][nb] > d){
                dist[x-1][y][r][nb] = d;
                dq.emplace_front(d, x-1, y, r, nb);
            }
        }
        // move right (cost 0, consume one r if available)
        if(S[x][y+1]=='.' && r < 1599){
            int nb = b | num[x][y+1];
            if(dist[x][y+1][r+1][nb] > d){
                dist[x][y+1][r+1][nb] = d;
                dq.emplace_front(d, x, y+1, r+1, nb);
            }
        }
        // move left (cost 0)
        if(S[x][y-1]=='.'){
            int nb = b | num[x][y-1];
            if(dist[x][y-1][r][nb] > d){
                dist[x][y-1][r][nb] = d;
                dq.emplace_front(d, x, y-1, r, nb);
            }
        }
    }

    int swx = gx - sx, swy = gy - sy;
    const int X = 30000;
    vector<bool> primes(X, true);
    primes[0] = primes[1] = false;
    for(int i = 2; i < X; i++){
        if(!primes[i]) continue;
        for(int j = i*2; j < X; j += i)
            primes[j] = false;
    }

    vector<ll> px, py;
    for(int i = 0; i < X; i++){
        if(i-swx >= 0 && i-swx < X && primes[i] && primes[i-swx])
            px.push_back(i);
    }
    for(int i = 0; i < X; i++){
        if(i-swy >= 0 && i-swy < X && primes[i] && primes[i-swy])
            py.push_back(i);
    }
    px.push_back(INF);
    py.push_back(INF);

    ll ans = INF;
    for(int r = 0; r < 1600; r++){
        ll d = dist[gx][gy][r][3];
        auto itx = lower_bound(px.begin(), px.end(), d);
        auto ity = lower_bound(py.begin(), py.end(), r);
        if(itx != px.end() && ity != py.end()){
            ll cand = (*itx + *ity) * 2 - swx - swy;
            ans = min(ans, cand);
        }
    }

    if(ans >= INF) cout << -1 << "\n";
    else           cout << ans << "\n";

    return 0;
}
0