結果

問題 No.3121 Prime Dance
ユーザー tassei903
提出日時 2025-04-19 00:29:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,596 ms / 2,000 ms
コード長 2,740 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 368,608 KB
最終ジャッジ日時 2025-04-19 00:29:30
合計ジャッジ時間 20,713 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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 = 10 ** 6 + 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)] for i in range(h * w)]
dist[0][sx][sy][0] = 0
dq = deque([(0, sx, sy, 0, 0)])
while dq:
    i, x, y, z, d = dq.popleft()
    # print(i, x, y, z, d)
    if dist[i][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
        ni = i
        if abs(dx):
            nz |= 1
            ni += 1
        if abs(dy):
            nz |= 2
        if 0 <= nx < h and 0 <= ny < w and c[nx][ny] != "#" and ni < h * w and dist[ni][nx][ny][nz] == -1:
            dist[ni][nx][ny][nz] = d + 1
            dq.append((ni, nx, ny, nz, d + 1))
inf = 10 ** 18
DX = gx - sx
DY = gy - sy
# for i in range(h * w):
#     print(dist[i][gx][gy][-1])
if all(dist[i][gx][gy][-1] == -1 for i in range(h * w)):
    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:
        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

for X in range(h * w):
    # print(X, dist[X][gx][gy][-1])
    if dist[X][gx][gy][-1] == -1:
        continue
    Y = dist[X][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