結果

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

ソースコード

diff # 

from collections import deque
import sys

# Generate primes up to 160 using Sieve of Eratosthenes
def generate_primes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit + 1, i):
                sieve[j] = False
    return {i for i, is_prime in enumerate(sieve) if is_prime}

# Directions: A(+1,0), B(-1,0), C(0,+1), D(0,-1)
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

    # Each state is (x, y, A, B, C, D)
    queue = deque()
    visited = set()
    queue.append((Sx, Sy, 0, 0, 0, 0, 0))  # x, y, A, B, C, D, total_steps
    visited.add((Sx, Sy, 0, 0, 0, 0))

    while queue:
        x, y, a, b, c, d, steps = queue.popleft()

        if (x, y) == (Gx, Gy) and all(move in primes for move in [a, b, c, d]):
            return steps

        for i, (dx, dy) in enumerate(DIRS):
            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 i == 0: na += 1
                elif i == 1: nb += 1
                elif i == 2: nc += 1
                elif i == 3: nd += 1

                state = (nx, ny, na, nb, nc, nd)
                if state not in visited:
                    visited.add(state)
                    queue.append((nx, ny, na, nb, nc, nd, steps + 1))

    return -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