結果

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

ソースコード

diff # 

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

# 1) Sieve primes up to n
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 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)]

    # Directions: 0=down,1=up,2=right,3=left
    DIRS = [(1,0),(-1,0),(0,1),(0,-1)]

    # 2) BFS from S to build a shortest‐path tree AND record the full reachable component
    q = deque()
    q.append((Sx, Sy))
    visited = [[False]*W for _ in range(H)]
    visited[Sx][Sy] = True
    parent = {}  # (x,y) -> ((px,py), dir_idx)
    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 G not reachable at all
    if not visited[Gx][Gy]:
        print(-1)
        return

    # 3) Reconstruct one shortest path S -> G
    path_dirs = []
    cur = (Gx, Gy)
    while cur != (Sx, Sy):
        (px,py), d = parent[cur]
        path_dirs.append(d)
        cur = (px,py)
    path_dirs.reverse()

    # 4) Count base‐path moves
    A0 = path_dirs.count(0)  # down
    B0 = path_dirs.count(1)  # up
    C0 = path_dirs.count(2)  # right
    D0 = path_dirs.count(3)  # left
    base_len = len(path_dirs)

    # 5) Check if we can insert vertical or horizontal 2‐step loops
    vert_ok = False
    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

    # 6) Sieve primes up to (base_len + 2000)
    LIMIT = base_len + 2000
    is_prime = sieve(LIMIT)

    # 7) Find minimal x≥0 so that A0+x and B0+x are both prime (if loops allowed)
    def find_shift(c0, d0, can_loop):
        # if no loops 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,1,2,...
        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

    x = find_shift(A0, B0, vert_ok)
    if x is None:
        print(-1)
        return

    y = find_shift(C0, D0, horz_ok)
    if y is None:
        print(-1)
        return

    # 8) Total moves = base_len + 2*(x + y)
    ans = base_len + 2*(x + y)
    print(ans)

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