結果

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

ソースコード

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):
        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 bfs_with_mask(H, W, grid, Sx, Sy, Gx, Gy, need_v, need_h, DIRS):
    """
    BFS from S to G, returning one *shortest* simple path that
      - if need_v is True, must include ≥1 vertical move (dx!=0)
      - if need_h is True, must include ≥1 horizontal move (dy!=0)
    Returns (A0,B0,C0,D0, base_len), or None if no such path.
    """
    # Build initial state
    # state = (x, y, used_v?, used_h?) depending on flags
    # We'll pack into a tuple of length 2/3/4
    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)
    target_checks = []
    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

    # BFS
    dq = deque([start])
    visited = {start}
    parent = {start: None}
    move_from = {}  # child_state -> (dx,dy)
    while dq:
        st = dq.popleft()
        x,y = st[0], st[1]
        uv = st[2] if need_v else False
        uh = st[3] if need_h else False
        # stop if we reached a valid target
        if is_target(st):
            # reconstruct path
            path = []
            cur = st
            while parent[cur] is not None:
                dx,dy = move_from[cur]
                path.append((dx,dy))
                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
        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 (dx!=0 and need_v)
            uh2 = uh or (dy!=0 and need_h)
            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  # no path satisfying mask

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)

    # Fixed neighbor order (any is fine for BFS min‐length; tie‐breaking might vary, but masks handle detours)
    DIRS = [(1,0),(-1,0),(0,1),(0,-1)]

    best = float('inf')
    # Try all 4 masks: 0=no required axis, 1=vertical, 2=horizontal, 3=both
    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
        # loops can only go where path has that axis
        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