結果

問題 No.3121 Prime Dance
ユーザー Nzt3
提出日時 2025-03-20 22:24:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 894 ms / 2,000 ms
コード長 2,249 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 183,484 KB
最終ジャッジ日時 2025-04-08 23:39:21
合計ジャッジ時間 9,916 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, a, c):
    return ((x*W+y)*H*W+a)*2+c


def idx2tup(n):
    c = n & 1
    n >>= 1
    a = n % (H*W)
    n //= H*W
    y = n % W
    x = n//W
    return x, y, a, c


dist = [IINF] * (H*W*H*W*2)
dist[tup2idx(Sx, Sy, 0, 0)] = 0
q = deque([tup2idx(Sx, Sy, 0, 0)])


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


while q:
    v = q.popleft()
    x, y, a, c = idx2tup(v)
    d = dist[v]
    # A
    if a+1 < H*W:
        x2, y2 = x-1, y
        v2 = tup2idx(x2, y2, a+1, c)
        if can_move(x2, y2) and dist[v2] > d:
            dist[v2] = d
            q.appendleft(v2)
    # B
    x2, y2 = x+1, y
    v2 = tup2idx(x2, y2, a, c)
    if can_move(x2, y2) and dist[v2] > d:
        dist[v2] = d
        q.appendleft(v2)

    # C
    x2, y2 = x, y-1
    v2 = tup2idx(x2, y2, a, 1)
    if can_move(x2, y2) and dist[v2] > d+1:
        dist[v2] = d+1
        q.append(v2)

    # D
    x2, y2 = x, y+1
    v2 = tup2idx(x2, y2, a, c)
    if can_move(x2, y2) and dist[v2] > d:
        dist[v2] = d
        q.appendleft(v2)

prime = [1] * (10**5)
prime[0] = 0
prime[1] = 0
for i in range(10**5):
    if not prime[i]:
        continue
    for j in range(i*i, 10**5, i):
        prime[j] = 0

pH = []
pW = []
for i in range(10**5-(Gx-Sx)):
    if prime[i] and prime[i+(Gx-Sx)]:
        pH.append(i)

for i in range(10**5-(Gy-Sy)):
    if prime[i] and prime[i+(Gy-Sy)]:
        pW.append(i)

ans = IINF


def lb(L, x):
    l, ge = -1, len(L)
    while ge-l > 1:
        mid = (ge+l) >> 1
        if L[mid] >= x:
            ge = mid
        else:
            l = mid
    return ge


for i in range(1, H*W):
    ch = lb(pH, i)
    cw = lb(pW, dist[tup2idx(Gx, Gy, i, 1)])
    if ch < len(pH) and cw < len(pW):
        ans = min(ans, pH[ch]*2+(Gx-Sx) + pW[cw]*2+(Gy-Sy))
if ans == IINF:
    print(-1)
else:
    print(ans)
0