結果

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

ソースコード

diff # 

import sys
from collections import deque

def sieve(n):
    
    is_prime = [False, False] + [True] * (n - 1)
    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 is_prime

def find_min_prime_sum(delta, is_prime, primes):
    
    INF = 10**18
    best = INF
    for q in primes:
        p = q + delta
        if p >= 2 and p < len(is_prime) and is_prime[p]:
            best = p + q
            break
    return best if best < INF else None

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sx, sy = map(int, input().split())
    gx, gy = map(int, input().split())
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1

    grid = [list(input().rstrip()) for _ in range(H)]
    seen = [[False]*W for _ in range(H)]
    q = deque()
    q.append((sx, sy))
    seen[sx][sy] = True
    comp = []
    while q:
        x, y = q.popleft()
        comp.append((x, y))
        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
            nx, ny = x+dx, y+dy
            if 0 <= nx < H and 0 <= ny < W and not seen[nx][ny] and grid[nx][ny] != '#':
                seen[nx][ny] = True
                q.append((nx, ny))

    if not seen[gx][gy]:
        print(-1)
        return

    vert_ok = False
    hori_ok = False
    for x, y in comp:
        
        if x+1 < H and seen[x+1][y]:
            vert_ok = True
        if y+1 < W and seen[x][y+1]:
            hori_ok = True
        if vert_ok and hori_ok:
            break

    if not vert_ok or not hori_ok:
        print(-1)
        return

    MAXP = 20000
    is_prime = sieve(MAXP)
    primes = [i for i in range(2, MAXP+1) if is_prime[i]]

    dx = gx - sx
    dy = gy - sy

    row_sum = find_min_prime_sum(dx, is_prime, primes)
    col_sum = find_min_prime_sum(dy, is_prime, primes)

    if row_sum is None or col_sum is None:
        print(-1)
    else:
        print(row_sum + col_sum)

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