結果

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

ソースコード

diff # 

from collections import deque

# Helper function to find prime numbers up to n using Sieve of Eratosthenes
def sieve_primes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return [i for i in range(limit + 1) if is_prime[i]]

# Directions: down, up, right, left
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def bfs(H, W, grid, S_x, S_y, G_x, G_y):
    # Perform BFS to find the shortest path from (S_x, S_y) to (G_x, G_y)
    queue = deque([(S_x, S_y, 0, 0, 0, 0)])  # (x, y, A, B, C, D)
    visited = set()
    visited.add((S_x, S_y))
    
    while queue:
        x, y, A, B, C, D = queue.popleft()
        
        # If we reached the goal, check if the counts A, B, C, D are all prime
        if (x, y) == (G_x, G_y):
            primes = sieve_primes(2000)
            if A in primes and B in primes and C in primes and D in primes:
                return A + B + C + D
        
        # Explore the four directions
        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] != '#':
                if (nx, ny) not in visited:
                    visited.add((nx, ny))
                    if i == 0:  # Moving down
                        queue.append((nx, ny, A + 1, B, C, D))
                    elif i == 1:  # Moving up
                        queue.append((nx, ny, A, B + 1, C, D))
                    elif i == 2:  # Moving right
                        queue.append((nx, ny, A, B, C + 1, D))
                    elif i == 3:  # Moving left
                        queue.append((nx, ny, A, B, C, D + 1))
    
    return -1

def solve():
    # Input parsing
    H, W = map(int, input().split())
    S_x, S_y = map(int, input().split())
    G_x, G_y = map(int, input().split())
    grid = [input().strip() for _ in range(H)]
    
    # Adjust for 0-based indexing
    S_x -= 1
    S_y -= 1
    G_x -= 1
    G_y -= 1
    
    # Perform BFS to find the minimum prime path
    result = bfs(H, W, grid, S_x, S_y, G_x, G_y)
    print(result)

# Call the solve function to execute the solution
solve()
0