結果

問題 No.3121 Prime Dance
ユーザー tassei903
提出日時 2025-04-19 00:14:30
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,589 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 233,584 KB
最終ジャッジ日時 2025-04-19 00:15:07
合計ジャッジ時間 30,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 1
other AC * 16 WA * 3 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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
if dist[gx][gy][-1] == -1:
    print(-1)
    exit()

# print(dist[gx][gy][-1])
# print(verdist[gx][gy][-1])
def f(a, b):
    return (a + b) // 2, (a - b) // 2
def p(x):
    if x < 2:
        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:
        assert False
        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:
                continue
            a, b = f(x, Y)
            # print(x,Y, a, b)
            if p(a) and p(b):
                ans = min(ans, a + b)
                break
        else:
            assert False
    return ans


ans = inf

X = verdist[gx][gy][-1]
Y = dist[gx][gy][-1] - X
ax = solve1(X, DX)
ay = solve1(Y, DY) 
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