結果

問題 No.3121 Prime Dance
ユーザー keymoon
提出日時 2025-04-19 18:39:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 938 ms / 2,000 ms
コード長 3,081 bytes
コンパイル時間 863 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 234,568 KB
最終ジャッジ日時 2025-04-19 18:39:30
合計ジャッジ時間 6,487 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def sieve(n):
    """Return a list is_prime[0..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 is_prime

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

    # reflect axes so that Δx, Δy >= 0
    if Gx < Sx:
        # mirror rows
        grid = grid[::-1]
        Sx = H-1 - Sx
        Gx = H-1 - Gx
    if Gy < Sy:
        # mirror columns
        for i in range(H):
            grid[i] = grid[i][::-1]
        Sy = W-1 - Sy
        Gy = W-1 - Gy

    if (Gy - Sy) == 0:
        H, W = W, H
        Sx, Sy = Sy, Sx
        Gx, Gy = Gy, Gx
        grid = [list(row) for row in zip(*grid)]

    dx = Gx - Sx
    dy = Gy - Sy

    # bound for primes: allow up to H*W + max(dx,dy) + margin
    bound = 1000
    is_prime = sieve(bound)

    # build candidate B-list (up moves) and D-list (left moves)
    Blist = [b for b in range(2, bound+1)
             if is_prime[b] and (b+dx)<=bound and is_prime[b+dx]]
    Dlist = [d for d in range(2, bound+1)
             if is_prime[d] and (d+dy)<=bound and is_prime[d+dy]]
    if not Blist or not Dlist:
        print(-1)
        return

    max_b = max(Blist)

    INF = 10**9
    # DP[x][y][b] = minimal d to reach (x,y) using b B-moves
    DP = [[[INF] * (max_b+1) for _ in range(W)] for __ in range(H)]
    dq = deque()
    DP[Sx][Sy][0] = 0
    dq.append((Sx, Sy, 0))

    # 0-1 BFS: cost = d-count; D moves cost 1, others cost 0
    while dq:
        x, y, b = dq.popleft()
        d = DP[x][y][b]
        # A: down (x+1, y)
        nx, ny, nb, nd = x+1, y, b, d
        if nx < H and grid[nx][ny] != '#' and DP[nx][ny][nb] > nd:
            DP[nx][ny][nb] = nd
            dq.appendleft((nx, ny, nb))
        # C: right (x, y+1)
        nx, ny, nb, nd = x, y+1, b, d
        if ny < W and grid[nx][ny] != '#' and DP[nx][ny][nb] > nd:
            DP[nx][ny][nb] = nd
            dq.appendleft((nx, ny, nb))
        # B: up (x-1, y)
        nx, ny, nb, nd = x-1, y, b+1, d
        if nx >= 0 and grid[nx][ny] != '#' and nb <= max_b and DP[nx][ny][nb] > nd:
            DP[nx][ny][nb] = nd
            dq.appendleft((nx, ny, nb))
        # D: left (x, y-1)
        nx, ny, nb, nd = x, y-1, b, d+1
        if ny >= 0 and grid[nx][ny] != '#' and DP[nx][ny][nb] > nd:
            DP[nx][ny][nb] = nd
            dq.append((nx, ny, nb))

    ans = INF
    # check each candidate b
    for b in Blist:
        for d in Dlist:
            d0 = DP[Gx][Gy][b]
            if d < d0: continue
            A = b + dx
            C = d + dy
            total = b + A + d + C
            if total < ans:
                ans = total

    print(ans if ans < INF else -1)

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