結果

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

ソースコード

diff # 

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())
    # convert to 0-index
    Sx -= 1; Sy -= 1; Gx -= 1; Gy -= 1
    grid = [list(input().rstrip()) for _ in range(H)]
    # pre-check reachability and shortest distance
    dist = [[-1]*W for _ in range(H)]
    dq = deque()
    dq.append((Sx, Sy))
    dist[Sx][Sy] = 0
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while dq:
        x, y = dq.popleft()
        for dx, dy in dirs:
            nx, ny = x+dx, y+dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and grid[nx][ny] != '#':
                dist[nx][ny] = dist[x][y] + 1
                dq.append((nx, ny))
    if dist[Gx][Gy] == -1:
        print(-1)
        return
    shortest = dist[Gx][Gy]
    dx = Gx - Sx
    dy = Gy - Sy
    # generate primes up to limit
    P_MAX = 1000
    is_prime = [True] * (P_MAX+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(P_MAX**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, P_MAX+1, i):
                is_prime[j] = False
    primes = [i for i, v in enumerate(is_prime) if v]
    # compute prime pairs for dx: A-B = dx
    pairs_x = []  # (A, B)
    if dx >= 0:
        for B in primes:
            A = B + dx
            if A <= P_MAX and is_prime[A]:
                pairs_x.append((A, B))
    else:
        # dx negative => A-B = dx => B = A - dx
        for A in primes:
            B = A - dx
            if B <= P_MAX and is_prime[B]:
                pairs_x.append((A, B))
    # for dy: C-D = dy
    pairs_y = []  # (C, D)
    if dy >= 0:
        for D in primes:
            C = D + dy
            if C <= P_MAX and is_prime[C]:
                pairs_y.append((C, D))
    else:
        for C in primes:
            D = C - dy
            if D <= P_MAX and is_prime[D]:
                pairs_y.append((C, D))
    if not pairs_x or not pairs_y:
        print(-1)
        return
    # build and sort combinations by total T = A+B+C+D
    combos = []
    for A, B in pairs_x:
        for C, Dv in pairs_y:
            T = A + B + C + Dv
            combos.append((T, A, B, C, Dv))
    combos.sort()
    # DP to check existence of walk of length T
    def can_reach_in_T(T):
        # simple DP: reachable positions after t steps
        cur = [[False]*W for _ in range(H)]
        cur[Sx][Sy] = True
        for _ in range(T):
            nxt = [[False]*W for _ in range(H)]
            for i in range(H):
                for j in range(W):
                    if not cur[i][j]:
                        continue
                    for dx_, dy_ in dirs:
                        ni, nj = i+dx_, j+dy_
                        if 0 <= ni < H and 0 <= nj < W and grid[ni][nj] != '#':
                            nxt[ni][nj] = True
            cur = nxt
        return cur[Gx][Gy]
    # try each combo in ascending T
    ans = -1
    for T, A, B, C, Dv in combos:
        # pruning by shortest path and parity
        if T < shortest: continue
        if (T - shortest) % 2 != 0: continue
        if can_reach_in_T(T):
            ans = T
            break
    print(ans)

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