結果

問題 No.3121 Prime Dance
ユーザー Nzt3
提出日時 2025-04-06 16:38:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 744 ms / 2,000 ms
コード長 2,969 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 81,492 KB
最終ジャッジ日時 2025-04-08 23:39:37
合計ジャッジ時間 10,340 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
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
C = [list(input()) for i in range(H)]

if Sx < Gx:
    Sx = H-1-Sx
    Gx = H-1-Gx
    C.reverse()

if Sy < Gy:
    Sy = W-1-Sy
    Gy = W-1-Gy
    for i in C:
        i.reverse()

IINF = 10**8


def tup2idx(x, y, f):
    return (x*W+y)*2+f


def idx2tup(n):
    f = n & 1
    n >>= 1
    y = n % W
    x = n//W
    return x, y, f


def move_ok(x, y):
    if x < 0 or x >= H or y < 0 or y >= W:
        return False
    return C[x][y] != "#"


def lb(A, x):
    ok = len(A)
    ng = -1
    while ok-ng > 1:
        mid = (ok+ng)//2
        if A[mid] >= x:
            ok = mid
        else:
            ng = mid
    return ok


MAX_P = 10**5
prime = [True]*(MAX_P)

prime[0] = False
prime[1] = False
for i in range(2, MAX_P):
    if not prime[i]:
        continue
    for j in range(i*i, MAX_P, i):
        prime[j] = False
pH, pW = [], []

for i in range(MAX_P):
    if i+(Sx-Gx) < MAX_P and prime[i] and prime[i+(Sx-Gx)]:
        pH.append(i)
    if i+(Sy-Gy) < MAX_P and prime[i] and prime[i+(Sy-Gy)]:
        pW.append(i)

ans = IINF
distmemo = [[] for _ in range(H*W)]
distmemo[0].append(tup2idx(Sx, Sy, 0))

for a in range(H*W):
    base = 0
    dist = [IINF]*(H*W*2)
    bfs = deque()
    while base < H*W or bfs:
        c = IINF
        if bfs:
            i = bfs.popleft()
            c = dist[i]
            bfs.appendleft(i)
        if base < c:
            for i in distmemo[base]:
                if dist[i] > base:
                    dist[i] = base
                    bfs.appendleft(i)
            base += 1
            continue
        i = bfs.popleft()
        x, y, f = idx2tup(i)
        c = dist[i]
        # B
        x2, y2 = x-1, y
        if move_ok(x2, y2) and dist[tup2idx(x2, y2, f)] > c:
            i2 = tup2idx(x2, y2, f)
            dist[i2] = c
            bfs.appendleft(i2)
        # C
        x2, y2 = x, y+1
        if move_ok(x2, y2) and dist[tup2idx(x2, y2, 1)] > c+1:
            i2 = tup2idx(x2, y2, 1)
            dist[i2] = c+1
            bfs.append(i2)
        # D
        x2, y2 = x, y-1
        if move_ok(x2, y2) and dist[tup2idx(x2, y2, 1)] > c:
            i2 = tup2idx(x2, y2, 1)
            dist[i2] = c
            bfs.appendleft(i2)
    if a > 0:
        c = dist[tup2idx(Gx, Gy, 1)]
        h = lb(pH, a)
        w = lb(pW, c)
        if h < len(pH) and w < len(pW) and pH[h]*2+(Sx-Gx)+pW[w]*2+(Sy-Gy) < ans:
            ans = pH[h]*2+(Sx-Gx)+pW[w]*2+(Sy-Gy)

    for i in distmemo:
        i.clear()
    for x in range(H):
        for y in range(W):
            for f in range(2):
                x2, y2 = x+1, y
                i = tup2idx(x, y, f)
                i2 = tup2idx(x2, y2, f)
                if move_ok(x2, y2) and dist[i] < H*W:
                    distmemo[dist[i]].append(i2)


if ans == IINF:
    print(-1)
else:
    print(ans)
0