結果

問題 No.3121 Prime Dance
コンテスト
ユーザー issaimaru
提出日時 2025-04-20 17:54:56
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,021 bytes
コンパイル時間 521 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2025-04-20 17:54:58
合計ジャッジ時間 2,200 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def sieve(n):
    is_prime = [True]*(n+1)
    is_prime[0]=is_prime[1]=False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j]=False
    return [i for i,pr in enumerate(is_prime) if pr], is_prime

def min_prime_pair_sum(delta, primes, is_prime):
    INF = 10**9
    best = INF
    
    for pB in primes:
        pA = pB + delta
        if pA < 2: 
            continue
        if pA < len(is_prime) and is_prime[pA]:
            best = min(best, pA + pB)
    return best if best < INF else None

def main():
    input = sys.stdin.readline
    H,W = map(int,input().split())
    Sx,Sy = map(lambda x:int(x)-1, input().split())
    Gx,Gy = map(lambda x:int(x)-1, input().split())
    grid = [list(input().rstrip()) for _ in range(H)]

    q = deque([(Sx,Sy)])
    vis = [[False]*W for _ in range(H)]
    vis[Sx][Sy]=True
    dr = [1,-1,0,0]
    dc = [0,0,1,-1]
    has_vert = False
    has_horiz = False
    while q:
        r,c = q.popleft()

        for nr,nc in [(r+1,c),(r-1,c)]:
            if 0<=nr<H and 0<=nc<W and grid[nr][nc] != '#' and vis[nr][nc]:
                has_vert = True

        for nr,nc in [(r,c+1),(r,c-1)]:
            if 0<=nr<H and 0<=nc<W and grid[nr][nc] != '#' and vis[nr][nc]:
                has_horiz = True

        for d in range(4):
            nr, nc = r+dr[d], c+dc[d]
            if 0<=nr<H and 0<=nc<W and not vis[nr][nc] and grid[nr][nc] != '#':
                vis[nr][nc]=True
                q.append((nr,nc))
    if not vis[Gx][Gy]:
        print(-1)
        return

    primes, is_prime = sieve(5000)

    dx = Gx - Sx
    dy = Gy - Sy

    if not has_vert:
        print(-1); return
    if not has_horiz:
        print(-1); return

    vx = min_prime_pair_sum(dx, primes, is_prime)
    vy = min_prime_pair_sum(dy, primes, is_prime)
    if vx is None or vy is None:
        print(-1)
    else:
        print(vx + vy)

if __name__ == "__main__":
    main()
0