結果

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

ソースコード

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):
    # if no loop allowed, only x=0
    if not can_loop:
        return 0 if c0<=LIMIT and d0<=LIMIT and is_prime[c0] and is_prime[d0] else None
    # otherwise scan x>=0
    for x in range(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):
    # BFS to get parent pointers and reachable-visited
    visited = [[False]*W for _ in range(H)]
    parent = {}
    q = deque([(Sx, Sy)])
    visited[Sx][Sy] = True
    while q:
        x, y = q.popleft()
        for dx, dy in 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), (dx,dy))
                q.append((nx,ny))
    # if G unreachable
    if not visited[Gx][Gy]:
        return float('inf')

    # reconstruct one shortest path by following parents
    path = []
    cur = (Gx, Gy)
    while cur != (Sx, Sy):
        (px, py), move = parent[cur]
        path.append(move)
        cur = (px, py)
    path.reverse()

    # count base-path moves
    A0 = sum(1 for dx,dy in path if dx == 1 and dy == 0)
    B0 = sum(1 for dx,dy in path if dx == -1 and dy == 0)
    C0 = sum(1 for dx,dy in path if dx == 0 and dy == 1)
    D0 = sum(1 for dx,dy in path if dx == 0 and dy == -1)
    base_len = len(path)

    # check if vertical/horizontal loops can be inserted anywhere in the 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

    # find minimal x and 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')

    # total = (A0+B0+C0+D0) + 2*(x+y) = base_len + 2*(x+y)
    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)]

    # sieve far enough: worst base_len ≤ H*W, loops ≤ +2000
    LIMIT = H*W + 2000
    is_prime = sieve(LIMIT)

    # three variants of neighbor order
    ΔV, ΔH = Gx - Sx, Gy - Sy
    DIRS1 = [(1,0), (-1,0), (0,1), (0,-1)]   # down, up, right, left
    DIRS2 = [(0,1), (0,-1), (1,0), (-1,0)]   # right, left, down, up
    # goal‐directed first
    order3 = []
    order3.append((1,0) if ΔV>0 else (-1,0))
    order3.append((0,1) if ΔH>0 else (0,-1))
    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