結果

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

ソースコード

diff # 

#!/usr/bin/env python3
import sys
from collections import deque

def solve():
    input = sys.stdin.readline

    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 = [list(input().rstrip()) for _ in range(H)]

    # 1) Plain BFS to check reachability + reconstruct one shortest path
    dist = [[-1]*W for _ in range(H)]
    parent = {}
    dq = deque([(Sx, Sy)])
    dist[Sx][Sy] = 0
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while dq:
        x,y = dq.popleft()
        if (x,y) == (Gx,Gy):
            break
        for dx,dy in dirs:
            nx, ny = x+dx, y+dy
            if 0 <= nx < H and 0 <= ny < W \
               and grid[nx][ny] != '#' and dist[nx][ny] < 0:
                dist[nx][ny] = dist[x][y] + 1
                parent[(nx,ny)] = (x,y)
                dq.append((nx,ny))

    if dist[Gx][Gy] < 0:
        print(-1)
        return

    # Reverse‐beam the path to count A0/B0/C0/D0
    path = []
    cur = (Gx, Gy)
    while cur != (Sx, Sy):
        path.append(cur)
        cur = parent[cur]
    path.append((Sx, Sy))
    path.reverse()

    A0 = B0 = C0 = D0 = 0
    for (x1,y1),(x2,y2) in zip(path, path[1:]):
        if x2 == x1+1:      A0 += 1  # down
        elif x2 == x1-1:    B0 += 1  # up
        elif y2 == y1+1:    C0 += 1  # right
        else:               D0 += 1  # left
    base_len = A0 + B0 + C0 + D0

    # 2) Check “loop‐edges” anywhere reachable
    #    vertical_edge_exists = can do a down–up loop somewhere
    #    horizontal_edge_exists = can do a right–left loop somewhere
    vert_ok = horiz_ok = False
    for i in range(H):
        for j in range(W):
            if dist[i][j] < 0 or grid[i][j] == '#':
                continue
            # vertical neighbor
            if i+1 < H and dist[i+1][j] >= 0 and grid[i+1][j] != '#':
                vert_ok = True
            # horizontal neighbor
            if j+1 < W and dist[i][j+1] >= 0 and grid[i][j+1] != '#':
                horiz_ok = True
            if vert_ok and horiz_ok:
                break
        if vert_ok and horiz_ok:
            break

    # 3) Sieve primes up to base_len+2000
    P_MAX = base_len + 2000
    is_prime = [True]*(P_MAX+1)
    is_prime[0] = is_prime[1] = False
    for p in range(2,int(P_MAX**0.5)+1):
        if is_prime[p]:
            for q in range(p*p, P_MAX+1, p):
                is_prime[q] = False

    # 4) Build x‐shifts for vertical (down–up) loops
    xs = []
    if A0>0 or vert_ok:
        # we can try any # of loops x ≥ 0
        limit = P_MAX - max(A0,B0)
        for x in range(limit+1):
            if is_prime[A0+x] and is_prime[B0+x]:
                xs.append(x)
    else:
        # no vertical loops available → must do x=0
        if is_prime[A0] and is_prime[B0]:
            xs = [0]

    # 5) Build y‐shifts for horizontal (right–left) loops
    ys = []
    if C0>0 or horiz_ok:
        limit = P_MAX - max(C0,D0)
        for y in range(limit+1):
            if is_prime[C0+y] and is_prime[D0+y]:
                ys.append(y)
    else:
        if is_prime[C0] and is_prime[D0]:
            ys = [0]

    if not xs or not ys:
        print(-1)
        return

    # 6) Minimize total T = base_len + 2x + 2y
    ans = min(base_len + 2*x + 2*y for x in xs for y in ys)
    print(ans)


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