結果

問題 No.3121 Prime Dance
ユーザー tassei903
提出日時 2025-04-18 23:55:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,907 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 233,452 KB
最終ジャッジ日時 2025-04-18 23:55:52
合計ジャッジ時間 31,064 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")

#######################################################################

N = 2 * 10 ** 7 + 100
aa = [0] * N
aa[0] = aa[1] = 1
for i in range(2, N):
    if aa[i]:continue
    for j in range(2 * i, N, i):
        aa[j] = 1

h, w = na()
sx, sy = na()
sx -= 1
sy -= 1
gx, gy = na()
gx -= 1
gy -= 1

c = [input() for i in range(h)]

from collections import deque
dist = [[[-1] * 4 for i in range(w)] for j in range(h)]
verdist = [[[-1] * 4 for i in range(w)] for j in range(h)]
dist[sx][sy][0] = 0
verdist[sx][sy][0] = 0
dq = deque([(sx, sy, 0, 0)])
while dq:
    x, y, z, d = dq.popleft()
    if dist[x][y][z] != d:
        continue
    for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nx = dx + x
        ny = dy + y
        nz = z
        if abs(dx):
            nz |= 1
        if abs(dy):
            nz |= 2
        if 0 <= nx < h and 0 <= ny < w and c[nx][ny] != "#" and dist[nx][ny][nz] == -1:
            dist[nx][ny][nz] = d + 1
            verdist[nx][ny][nz] = verdist[x][y][z] + abs(dx)
            dq.append((nx, ny, nz, d + 1))
inf = 10 ** 18
DX = gx - sx
DY = gy - sy
# print(dist[gx][gy])
# print(verdist[gx][gy])
def f(a, b):
    return (a + b) // 2, (a - b) // 2
def p(x):
    if x < 2 or x >= N:
        return False    
    return aa[x] == 0

def solve1(X, Y):#minimize a + b s.t. a + b >= x and a - b == Y and a is prime and b is prime
    ans = inf

    if Y % 2 == 1:
        a = 2
        b = a - Y
        if p(b):
            ans = min(ans, a + b)
        b = 2
        a = b + Y
        if p(a):
            ans = min(ans, a + b)
    else:
        for x in range(X, N):
            if (x - Y) % 2 == 0:
                continue
            a, b = f(x, Y)
            # print(x,Y, a, b)
            if p(a) and p(b):
                ans = min(ans, a + b)
                break
    # print(X, Y, ans)
    return ans
def solve2(X, Y):
    a, b = f(X, Y)
    if p(a) and p(b):
        return a + b
    else:
        return inf


ans = inf
for i in range(4):
    if verdist[gx][gy][i] != -1 and dist[gx][gy][i] != -1:
        X = verdist[gx][gy][i]
        Y = dist[gx][gy][i] - X
        if i % 2:
            ax = solve1(X, DX)
        else:
            ax = solve2(X, DX)
        if i // 2:
            ay = solve1(Y, DY)
        else:
            ay = solve2(Y, DY)
        # print(i, X, DX, ax, ay)
        
        ans = min(ans, ax + ay)
# print(solve1(3, 120))

# for i in range(1, 1600):
#     for j in range(0, 40, 2):
#         print(i, j, solve1(i,j))
#         if solve1(i, j) == inf:
#             print(i, j)


# print(solve1(2, 0))
if ans == inf:
    print(-1)
else:
    print(ans)
0