結果

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

ソースコード

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):
    """Return smallest x≥0 so that c0+x and d0+x are both prime.
       If can_loop is False, only x=0 is allowed (and we require c0,d0 themselves to be prime)."""
    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(LIMIT+1):
        if is_prime[c0+x] and is_prime[d0+x]:
            return x
    return None

def bfs_with_mask(H, W, grid, Sx, Sy, Gx, Gy, need_v, need_h, DIRS):
    """Run BFS with additional requirements on vertical and horizontal movements in the path."""
    def make_state(x, y, uv, uh):
        if need_v and need_h:   return (x,y,uv,uh)
        if need_v:              return (x,y,uv)
        if need_h:              return (x,y,uh)
        return (x,y)

    start = make_state(Sx, Sy, False, False)
    
    if need_v and need_h:
        def is_target(st): return st[0]==Gx and st[1]==Gy and st[2] and st[3]
    elif need_v:
        def is_target(st): return st[0]==Gx and st[1]==Gy and st[2]
    elif need_h:
        def is_target(st): return st[0]==Gx and st[1]==Gy and st[2]
    else:
        def is_target(st): return st[0]==Gx and st[1]==Gy

    dq = deque([start])
    visited = {start}
    parent = {start: None}
    move_from = {}

    while dq:
        st = dq.popleft()
        x, y = st[0], st[1]
        idx = 2
        if need_v:
            uv = st[idx]
            idx += 1
        else:
            uv = False
        if need_h:
            uh = st[idx]
        else:
            uh = False

        if is_target(st):
            # Reconstruct the path
            path = []
            cur = st
            while parent[cur] is not None:
                path.append(move_from[cur])
                cur = parent[cur]
            path.reverse()
            # Count 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)
            return A0, B0, C0, D0, len(path)

        # Expand neighbors
        for dx, dy in DIRS:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W): continue
            if grid[nx][ny] == '#': continue
            uv2 = uv or (need_v and dx != 0)
            uh2 = uh or (need_h and dy != 0)
            nxt = make_state(nx, ny, uv2, uh2)
            if nxt in visited: continue
            visited.add(nxt)
            parent[nxt] = st
            move_from[nxt] = (dx, dy)
            dq.append(nxt)

    return None

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)]

    # Special case where start == goal
    if Sx == Gx and Sy == Gy:
        print(0)
        return

    LIMIT = H * W + 2000
    is_prime = sieve(LIMIT)

    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    best = float('inf')

    # Try masks 0..3
    for mask in range(4):
        need_v = bool(mask & 1)
        need_h = bool(mask & 2)
        res = bfs_with_mask(H, W, grid, Sx, Sy, Gx, Gy, need_v, need_h, DIRS)
        if res is None:
            continue
        A0, B0, C0, D0, base_len = res

        # Only allow loops along axes actually used in the base path
        can_vert = (A0 + B0) > 0
        can_horz = (C0 + D0) > 0

        x = find_shift(A0, B0, can_vert, is_prime, LIMIT)
        if x is None: continue
        y = find_shift(C0, D0, can_horz, is_prime, LIMIT)
        if y is None: continue

        total = base_len + 2 * (x + y)
        if total < best:
            best = total

    print(best if best < float('inf') else -1)

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