結果

問題 No.3121 Prime Dance
ユーザー Mistletoe
提出日時 2025-04-19 20:35:45
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,880 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2025-04-19 20:35:48
合計ジャッジ時間 2,142 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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):
    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):
    # build state‐tuple factory
    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 and target predicate
    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()
        # unpack x,y,uv,uh properly
        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 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)]

    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