結果

問題 No.3121 Prime Dance
コンテスト
ユーザー mathphilia
提出日時 2025-04-19 11:13:20
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,934 bytes
コンパイル時間 129 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-04-19 11:13:25
合計ジャッジ時間 2,487 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections,sympy
height,width=map(int,input().split())
sx,sy=map(lambda x:int(x)-1,input().split())
gx,gy=map(lambda x:int(x)-1,input().split())
board=[]
for _ in range(height):
    row=input()
    board.append([cell!='#' for cell in row])
queue=collections.deque([(sx,sy)])
visited=set()
reachable=False
while queue:
    x,y=queue.popleft()
    if (x,y) in visited:
        continue
    visited.add((x,y))
    if (x,y)==(gx,gy):
        reachable=True
        break
    for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0<=x+dx<height and 0<=y+dy<width and board[x+dx][y+dy]:
            queue.append((x+dx,y+dy))
if not reachable:
    print(-1)
    exit()
dx=abs(sx-gx)
dx_add=0
dy=abs(sy-gy)
dy_add=0
if dx==0:
    left,right=sorted([sy,gy])
    tmp=float('inf')
    for current in range(left,-1,-1):
        if not board[sx][current]:
            break
        elif (0<sx and board[sx-1][current]) or (sx<height-1 and board[sx+1][current]):
            tmp=min(tmp,left-current)
            break
    for current in range(right,height):
        if not board[sx][current]:
            break
        elif (0<sx and board[sx-1][current]) or (sx<height-1 and board[sx+1][current]):
            tmp=min(tmp,current-right)
            break
    for current in range(left+1,right):
        if not board[sx][current]:
            break
        elif (0<sx and board[sx-1][current]) or (sx<height-1 and board[sx+1][current]):
            tmp=0
            break
    if tmp<float('inf'):
        dy_add=tmp
    else:
        print(-1)
        exit()
if dy==0:
    upper,lower=sorted([sx,gx])
    tmp=1000
    for current in range(upper-1,-1,-1):
        if not board[current][sy]:
            break
        elif (0<sy and board[current][sy-1]) or (sy<width-1 and board[current][sy+1]):
            tmp=min(tmp,upper-current)
            break
    for current in range(lower+1,height):
        if not board[current][sy]:
            break
        elif (0<sy and board[current][sy-1]) or (sy<width-1 and board[current][sy+1]):
            tmp=min(tmp,current-lower)
            break
    for current in range(upper,lower+1):
        if not board[current][sy]:
            break
        elif (0<sy and board[current][sy-1]) or (sy<width-1 and board[current][sy+1]):
            tmp=0
            break
    if tmp<float('inf'):
        dx_add=tmp
    else:
        print(-1)
        exit()
if dx==0 or dx%2==1:
    if (not sympy.isprime(2+dx)) or (2<dx_add):
        print(-1)
        exit()
    else:
        x_score=4+dx
else:
    for p in sympy.primerange(dx_add,1<<64):
        if sympy.isprime(p+dx):
            x_score=2*p+dx
            break
if dy==0 or dy%2==1:
    if (not sympy.isprime(2+dy)) or (2<dy_add):
        print(-1)
        exit()
    else:
        y_score=4+dy
else:
    for p in sympy.primerange(dy_add,1<<64):
        if sympy.isprime(p+dy):
            y_score=2*p+dy
            break
print(x_score+y_score)
0