結果

問題 No.3121 Prime Dance
ユーザー titia
提出日時 2025-05-10 02:58:28
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,848 bytes
コンパイル時間 549 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 849,576 KB
最終ジャッジ日時 2025-05-10 02:58:35
合計ジャッジ時間 5,928 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from collections import deque

# x以下の素数の列挙,素因数分解,約数の列挙
    
x=200000
L=round(x**(1/2))

Primelist=[i for i in range(x+1)]
Primelist[1]=0 # 1は素数でないので0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0

Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]
SET=set(Primes)

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

MAP=[input().strip() for i in range(H)]
c=500
DP=[[[[1<<30]*W for i in range(H)] for j in range(c)] for k in range(c)]

Q=deque()
Q.append((0,0,sx,sy))
DP[0][0][sx][sy]=0

while Q:
    #print(Q)
    left,down,x,y=Q.popleft()
    now=DP[left][down][x][y]

    if x-1>=0 and left+1<c and MAP[x-1][y]!="#" and DP[left+1][down][x-1][y]>now+1:
        DP[left+1][down][x-1][y]=now+1
        Q.append((left+1,down,x-1,y))

    if y-1>=0 and down+1<c and MAP[x][y-1]!="#" and DP[left][down+1][x][y-1]>now+1:
        DP[left][down+1][x][y-1]=now+1
        Q.append((left,down+1,x,y-1))

    if x+1<H and MAP[x+1][y]!="#" and DP[left][down][x+1][y]>now+1:
        DP[left][down][x+1][y]=now+1
        Q.append((left,down,x+1,y))

    if y+1<W and MAP[x][y+1]!="#" and DP[left][down][x][y+1]>now+1:
        DP[left][down][x][y+1]=now+1
        Q.append((left,down,x,y+1))

ANS=1<<60
for i in range(c):
    for j in range(c):
        count=DP[i][j][gx][gy]

        if count>=1<<29:
            continue
        left=i
        down=j
        right=(gx-sx)+left
        up=(gy-sy)+down

        #print(left,down,right,up,count)

        if left in SET and down in SET and right in SET and up in SET:
            ANS=min(ANS,count)

if ANS>10**9:
    print(-1)
else:
    print(ANS)
0