結果

問題 No.3121 Prime Dance
ユーザー keymoon
提出日時 2025-04-19 07:26:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,731 bytes
コンパイル時間 274 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 235,224 KB
最終ジャッジ日時 2025-04-19 07:26:47
合計ジャッジ時間 10,665 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 10 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

# written by ChatGPT o4-mini-high (really sorry)

import sys
from collections import deque

def input():
    return sys.stdin.readline()

def sieve(n):
    """Return a list `is_prime` of length n+1 where is_prime[i] is True if i is prime."""
    is_prime = [False, False] + [True] * (n - 1)
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return is_prime

def find_prime_pairs(delta, is_prime):
    """
    For a given integer delta = |dr|, find all pairs of primes (p, q) such that
    p - q = delta. Return list of (larger, smaller) = (p, q).
    """
    pairs = []
    max_p = len(is_prime) - 1
    # try q from smallest prime up, such that q + delta <= max_p
    for q in range(2, max_p - delta + 1):
        if is_prime[q]:
            p = q + delta
            if p <= max_p and is_prime[p]:
                pairs.append((p, q))
    return pairs

def solve():
    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 = []
    for _ in range(H):
        row = input().strip().replace(" ", "")
        grid.append(row)

    dr = gx - sx
    dc = gy - sy
    # maximum delta we'll need primes up to about H+W
    MAXP = (H + W) * 2 + 100
    is_prime = sieve(MAXP)

    # build vertical prime pairs (A, B)
    delta_r = abs(dr)
    vp = find_prime_pairs(delta_r, is_prime)
    vertical_pairs = []
    for p, q in vp:
        if dr >= 0:
            vertical_pairs.append((p, q))  # A = p (down), B = q (up)
        else:
            vertical_pairs.append((q, p))  # B = p (up),   A = q (down)

    # build horizontal prime pairs (C, D)
    delta_c = abs(dc)
    hp = find_prime_pairs(delta_c, is_prime)
    horizontal_pairs = []
    for p, q in hp:
        if dc >= 0:
            horizontal_pairs.append((p, q))  # C = p (right), D = q (left)
        else:
            horizontal_pairs.append((q, p))  # D = p (left),  C = q (right)

    # if no possible prime pairs in either dimension, impossible
    if not vertical_pairs or not horizontal_pairs:
        print(-1)
        return

    # build all candidate (A,B,C,D) and sort by total moves
    candidates = []
    for A, B in vertical_pairs:
        for C, D in horizontal_pairs:
            T = A + B + C + D
            candidates.append((T, A, B, C, D))
    candidates.sort()

    # BFS for each candidate in increasing total moves
    for T, A, B, C, D in candidates:
        # early skip if total moves smaller than Manhattan distance
        if T < abs(dr) + abs(dc):
            continue

        # BFS state: (x, y, a_used, b_used, c_used, d_used)
        # prune: a_used <= A, etc., and steps <= T
        start = (sx, sy, 0, 0, 0, 0)
        dq = deque([start])
        visited = set([start])
        found = False

        while dq:
            x, y, a_u, b_u, c_u, d_u = dq.popleft()
            steps = a_u + b_u + c_u + d_u
            # if we've used up all moves, check if at goal
            if steps == T:
                if (x, y) == (gx, gy) and a_u == A and b_u == B and c_u == C and d_u == D:
                    print(T)
                    return
                continue

            # try each direction if we still need that move
            # Move A: down
            if a_u < A:
                nx, ny = x + 1, y
                if 0 <= nx < H and grid[nx][ny] != '#':
                    ns = (nx, ny, a_u + 1, b_u, c_u, d_u)
                    if ns not in visited:
                        visited.add(ns)
                        dq.append(ns)
            # Move B: up
            if b_u < B:
                nx, ny = x - 1, y
                if 0 <= nx < H and grid[nx][ny] != '#':
                    ns = (nx, ny, a_u, b_u + 1, c_u, d_u)
                    if ns not in visited:
                        visited.add(ns)
                        dq.append(ns)
            # Move C: right
            if c_u < C:
                nx, ny = x, y + 1
                if 0 <= ny < W and grid[x][ny] != '#':
                    ns = (x, ny, a_u, b_u, c_u + 1, d_u)
                    if ns not in visited:
                        visited.add(ns)
                        dq.append(ns)
            # Move D: left
            if d_u < D:
                nx, ny = x, y - 1
                if 0 <= ny < W and grid[x][ny] != '#':
                    ns = (x, ny, a_u, b_u, c_u, d_u + 1)
                    if ns not in visited:
                        visited.add(ns)
                        dq.append(ns)

        # if BFS ends without finding, try next candidate
    # no candidate works
    print(-1)

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