結果

問題 No.3121 Prime Dance
コンテスト
ユーザー issaimaru
提出日時 2025-04-20 18:02:08
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,013 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2025-04-20 18:02:10
合計ジャッジ時間 1,855 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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**9
    best = INF
    for q in primes:
        p = q + delta
        if p >= 2 and p < len(is_prime) and is_prime[p]:
            best = min(best, p + q)
    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)]
    dq = deque([(sx, sy)])
    seen[sx][sy] = True
    comp = []
    while dq:
        x, y = dq.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
                dq.append((nx,ny))

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


    vert_ok = False
    hori_ok = False
    for x, y in comp:
        for dx, dy in ((1,0),(0,1)):
            nx, ny = x+dx, y+dy
            if 0 <= nx < H and 0 <= ny < W and seen[nx][ny] and grid[nx][ny] != '#':
                if dx != 0: vert_ok = True
                if dy != 0: hori_ok = True

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

    MAXP = 500
    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