結果

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

ソースコード

diff # 

#!/usr/bin/env python3
import sys
from collections import deque

def solve():
    input = sys.stdin.readline

    H, W = map(int, input().split())
    Sx, Sy = map(int, input().split())
    Gx, Gy = map(int, input().split())
    # 0‑index
    Sx -= 1; Sy -= 1
    Gx -= 1; Gy -= 1

    grid = [list(input().rstrip()) for _ in range(H)]

    # 1) BFS for reachability & shortest-path parents
    dist = [[-1]*W for _ in range(H)]
    parent = {}
    dq = deque([(Sx, Sy)])
    dist[Sx][Sy] = 0
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while dq:
        x, y = dq.popleft()
        if (x,y) == (Gx,Gy):
            break
        for dx, dy in dirs:
            nx, ny = x+dx, y+dy
            if 0 <= nx < H and 0 <= ny < W \
               and grid[nx][ny] != '#' and dist[nx][ny] < 0:
                dist[nx][ny] = dist[x][y] + 1
                parent[(nx,ny)] = (x,y)
                dq.append((nx,ny))

    if dist[Gx][Gy] < 0:
        print(-1)
        return

    # 2) Reconstruct *one* shortest path and count its directional moves
    path = []
    cur = (Gx, Gy)
    while cur != (Sx, Sy):
        path.append(cur)
        cur = parent[cur]
    path.append((Sx, Sy))
    path.reverse()

    A0 = B0 = C0 = D0 = 0
    for (x1,y1), (x2,y2) in zip(path, path[1:]):
        if x2 == x1 + 1:      A0 += 1  # down
        elif x2 == x1 - 1:    B0 += 1  # up
        elif y2 == y1 + 1:    C0 += 1  # right
        else:                 D0 += 1  # left

    base_len = A0 + B0 + C0 + D0

    # 3) sieve primes up to ~2000
    P_MAX = 2000
    is_prime = [True]*(P_MAX+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(P_MAX**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, P_MAX+1, i):
                is_prime[j] = False

    # 4) build x-list: want A0+x and B0+x both prime
    xs = []
    for x in range(0, P_MAX+1 - max(A0,B0)):
        if is_prime[A0 + x] and is_prime[B0 + x]:
            xs.append(x)

    # 5) build y-list: want C0+y and D0+y both prime
    ys = []
    for y in range(0, P_MAX+1 - max(C0,D0)):
        if is_prime[C0 + y] and is_prime[D0 + y]:
            ys.append(y)

    if not xs or not ys:
        print(-1)
        return

    # 6) take the best
    ans = None
    for x in xs:
        for y in ys:
            T = base_len + 2*x + 2*y
            if ans is None or T < ans:
                ans = T

    print(ans)


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