結果

問題 No.3121 Prime Dance
ユーザー hirayuu_yc
提出日時 2025-04-19 12:39:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,013 bytes
コンパイル時間 505 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 665,036 KB
最終ジャッジ日時 2025-04-19 12:40:28
合計ジャッジ時間 28,016 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 11 WA * 9 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
from bisect import bisect_left
H,W=map(int,input().split())
sx,sy=map(int,input().split())
gx,gy=map(int,input().split())
S=["#"*(W+2) for i in range(H+2)]
for i in range(H):
    S[i+1]="#"+input()+"#"
S=[list(s) for s in S]
S[sx][sy]="."
S[gx][gy]="."
H+=2
W+=2
num=[[0]*W for i in range(H)]
for i in range(1,H-1):
    for j in range(1,W-1):
        if S[i-1][j]=="." or S[i+1][j]==".":
            num[i][j]^=1
        if S[i][j-1]=="." or S[i][j+1]==".":
            num[i][j]^=2
dist=[[[[1<<60]*4 for i in range(2000)] for i in range(W)] for i in range(H)]
dist[sx][sy][0][num[sx][sy]]=0
vert=deque()
vert.append((0,sx,sy,0,num[sx][sy]))
while vert:
    d,x,y,r,b=vert.popleft()
    if dist[x][y][r][b]!=d:
        continue
    if S[x+1][y]==".":
        if dist[x+1][y][r][b|num[x+1][y]]>d+1:
            dist[x+1][y][r][b|num[x+1][y]]=d+1
            vert.append((d+1,x+1,y,r,b|num[x+1][y]))
    if S[x-1][y]==".":
        if dist[x-1][y][r][b|num[x-1][y]]>d:
            dist[x-1][y][r][b|num[x-1][y]]=d
            vert.appendleft((d,x-1,y,r,b|num[x-1][y]))
    if S[x][y+1]==".":
        if r!=1999 and dist[x][y+1][r+1][b|num[x][y+1]]>d:
            dist[x][y+1][r+1][b|num[x][y+1]]=d
            vert.appendleft((d,x,y+1,r+1,b|num[x][y+1]))
    if S[x][y-1]==".":
        if dist[x][y-1][r][b|num[x][y-1]]>d:
            dist[x][y-1][r][b|num[x][y-1]]=d
            vert.appendleft((d,x,y-1,r,b|num[x][y-1]))
swx=gx-sx
swy=gy-sy
primes=[1]*100000
primes[0]=0
primes[1]=0
for i in range(2,100000):
    for j in range(i*2,100000,i):
        primes[j]=0
px=[]
py=[]
for i in range(100000):
    if 0<=i+swx<100000 and primes[i] and primes[i+swx]:
        px.append(i)
for i in range(100000):
    if 0<=i+swy<100000 and primes[i] and primes[i+swy]:
        py.append(i)
px.append(1<<60)
py.append(1<<60)
ans=1<<60
for i in range(2000):
    ans=min(ans,(px[bisect_left(px,dist[gx][gy][i][3])]+py[bisect_left(py,i)])*2+swx+swy)
if ans>=(1<<60):
    print(-1)
else:
    print(ans)
0