結果

問題 No.3121 Prime Dance
ユーザー Mistletoe
提出日時 2025-04-19 20:03:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,240 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2025-04-19 20:03:09
合計ジャッジ時間 3,057 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())
    Sx -= 1; Sy -= 1; Gx -= 1; Gy -= 1
    
    grid = [list(input().rstrip()) for _ in range(H)]
    
    # BFS to find the shortest distance
    dist = [[-1] * W for _ in range(H)]
    dq = deque([(Sx, Sy)])
    dist[Sx][Sy] = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while dq:
        x, y = dq.popleft()
        for dx, dy in directions:
            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
    
    # Prime sieve to generate primes up to a reasonable 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]
    
    # Generate prime pairs for dx (A-B = dx)
    pairs_x = []
    if dx >= 0:
        for B in primes:
            A = B + dx
            if A <= P_MAX and is_prime[A]:
                pairs_x.append((A, B))
    else:
        for A in primes:
            B = A - dx
            if B <= P_MAX and is_prime[B]:
                pairs_x.append((A, B))
    
    # Generate prime pairs for dy (C-D = dy)
    pairs_y = []
    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
    
    # Generate all combinations of prime steps
    combos = []
    for A, B in pairs_x:
        for C, D in pairs_y:
            T = A + B + C + D
            combos.append((T, A, B, C, D))
    
    combos.sort()
    
    # DP or BFS to check if we can reach the goal with exactly T steps
    def can_reach_in_T(T):
        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 directions:
                        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 combination in increasing T
    ans = -1
    for T, A, B, C, D in combos:
        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