結果

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

ソースコード

diff # 

from collections import deque
import sys
input = sys.stdin.readline

def sieve(n):
    is_prime = [True]*(n+1)
    if n >= 0: is_prime[0] = False
    if n >= 1: 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 find_shift(c0, d0, can_loop, is_prime, LIMIT):
    """Find minimal x >= 0 s.t. c0+x and d0+x are prime, 
       but if can_loop is False only x=0 is allowed."""
    if not can_loop:
        return 0 if c0<=LIMIT and d0<=LIMIT and is_prime[c0] and is_prime[d0] else None
    for x in range(0, LIMIT+1):
        cc = c0 + x
        dd = d0 + x
        if cc <= LIMIT and dd <= LIMIT and is_prime[cc] and is_prime[dd]:
            return x
    return None

def try_variant(H, W, grid, Sx, Sy, Gx, Gy, DIRS, is_prime, LIMIT):
    # 1) BFS from S to build shortest‐path tree (parent) and visited
    q = deque()
    q.append((Sx, Sy))
    visited = [[False]*W for _ in range(H)]
    visited[Sx][Sy] = True
    parent = {}
    while q:
        x,y = q.popleft()
        for d,(dx,dy) in enumerate(DIRS):
            nx,ny = x+dx, y+dy
            if 0<=nx<H and 0<=ny<W and not visited[nx][ny] and grid[nx][ny] != '#':
                visited[nx][ny] = True
                parent[(nx,ny)] = ((x,y), d)
                q.append((nx,ny))
    if not visited[Gx][Gy]:
        return float('inf')
    # 2) Reconstruct one shortest path S->G
    path = []
    cur = (Gx,Gy)
    while cur != (Sx,Sy):
        (px,py), d = parent[cur]
        path.append(d)
        cur = (px,py)
    path.reverse()
    A0 = path.count(0)  # down
    B0 = path.count(1)  # up
    C0 = path.count(2)  # right
    D0 = path.count(3)  # left
    base_len = len(path)
    # 3) Check if any vertical / horizontal adjacency exists in visited‐component
    vert_ok = horz_ok = False
    for x in range(H):
        for y in range(W):
            if visited[x][y]:
                if x+1<H and visited[x+1][y]:
                    vert_ok = True
                if y+1<W and visited[x][y+1]:
                    horz_ok = True
            if vert_ok and horz_ok:
                break
        if vert_ok and horz_ok:
            break
    # 4) find minimal loops x,y
    x = find_shift(A0, B0, vert_ok, is_prime, LIMIT)
    if x is None:
        return float('inf')
    y = find_shift(C0, D0, horz_ok, is_prime, LIMIT)
    if y is None:
        return float('inf')
    return base_len + 2*(x + y)

def solve():
    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 = [input().rstrip() for _ in range(H)]

    # Pre‑sieve primes up to (max possible base_len + 2000)
    LIMIT = H*W + 2000
    is_prime = sieve(LIMIT)

    # three neighbor‐orders → three shortest‐path extractions
    ΔV = Gx - Sx
    ΔH = Gy - Sy

    # 1) vertical‐first (down, up, right, left)
    DIRS1 = [(1,0),(-1,0),(0,1),(0,-1)]
    # 2) horizontal‑first (right, left, down, up)
    DIRS2 = [(0,1),(0,-1),(1,0),(-1,0)]
    # 3) goal‐directed first
    order3 = []
    if ΔV > 0: order3.append((1,0))   # down
    else:      order3.append((-1,0))  # up
    if ΔH > 0: order3.append((0,1))   # right
    else:      order3.append((0,-1))  # left
    # then the other two
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
        if d not in order3:
            order3.append(d)
    DIRS3 = order3

    ans = min(
        try_variant(H,W,grid,Sx,Sy,Gx,Gy,DIRS1,is_prime,LIMIT),
        try_variant(H,W,grid,Sx,Sy,Gx,Gy,DIRS2,is_prime,LIMIT),
        try_variant(H,W,grid,Sx,Sy,Gx,Gy,DIRS3,is_prime,LIMIT),
    )
    print(ans if ans < float('inf') else -1)

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