結果

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

ソースコード

diff # 

from itertools import product
from collections import deque

# Generate prime numbers up to n
def generate_primes(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, n + 1, i):
                sieve[j] = False
    return [i for i, is_p in enumerate(sieve) if is_p]

# BFS to check if path is possible with exact A, B, C, D moves
def path_exists(grid, sx, sy, gx, gy, A, B, C, D):
    H, W = len(grid), len(grid[0])
    queue = deque()
    queue.append((sx, sy, A, B, C, D))
    visited = set()
    visited.add((sx, sy, A, B, C, D))
    
    while queue:
        x, y, a, b, c, d = queue.popleft()
        if (x, y) == (gx, gy) and a == b == c == d == 0:
            return True

        for dx, dy, use in [(1, 0, 'A'), (-1, 0, 'B'), (0, 1, 'C'), (0, -1, 'D')]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] != '#':
                na, nb, nc, nd = a, b, c, d
                if use == 'A' and na > 0: na -= 1
                elif use == 'B' and nb > 0: nb -= 1
                elif use == 'C' and nc > 0: nc -= 1
                elif use == 'D' and nd > 0: nd -= 1
                else: continue
                state = (nx, ny, na, nb, nc, nd)
                if state not in visited:
                    visited.add(state)
                    queue.append(state)
    return False

def solve(H, W, Sx, Sy, Gx, Gy, grid):
    Sx -= 1
    Sy -= 1
    Gx -= 1
    Gy -= 1

    dx = Gx - Sx
    dy = Gy - Sy

    primes = generate_primes(40)
    min_ops = float('inf')

    for A, B in product(primes, repeat=2):
        if A - B != dx:
            continue
        for C, D in product(primes, repeat=2):
            if C - D != dy:
                continue
            total_ops = A + B + C + D
            if path_exists(grid, Sx, Sy, Gx, Gy, A, B, C, D):
                min_ops = min(min_ops, total_ops)

    return min_ops if min_ops != float('inf') else -1

# Input parsing
def main():
    H, W = map(int, input().split())
    Sx, Sy, Gx, Gy = map(int, input().split())
    grid = [input().strip() for _ in range(H)]
    print(solve(H, W, Sx, Sy, Gx, Gy, grid))

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