結果

問題 No.3121 Prime Dance
ユーザー shibh308
提出日時 2025-04-20 04:23:44
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,607 bytes
コンパイル時間 519 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2025-04-20 04:23:47
合計ジャッジ時間 2,226 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def solve():
    H,W = map(int,input().split())
    Sx,Sy = map(lambda x: int(x)-1, input().split())
    Gx,Gy = map(lambda x: int(x)-1, input().split())
    grid = [list(input().strip()) for _ in range(H)]

    dist = [[-1]*W for _ in range(H)]
    parent = [[None]*W for _ in range(H)]
    q = deque()
    dist[Sx][Sy] = 0
    q.append((Sx,Sy))
    while q:
        x,y = q.popleft()
        for dx,dy,op in [(1,0,'A'),(-1,0,'B'),(0,1,'C'),(0,-1,'D')]:
            nx,ny = x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and grid[nx][ny] != '#' and dist[nx][ny]==-1:
                dist[nx][ny] = dist[x][y]+1
                parent[nx][ny] = (x,y,op)
                q.append((nx,ny))
    if dist[Gx][Gy] < 0:
        print(-1)
        return

    A0=B0=C0=D0 = 0
    cx,cy = Gx,Gy
    while (cx,cy) != (Sx,Sy):
        px,py,op = parent[cx][cy]
        if op=='A': A0 += 1
        elif op=='B': B0 += 1
        elif op=='C': C0 += 1
        else:         D0 += 1
        cx,cy = px,py

    dx = A0 - B0
    dy = C0 - D0

    visited = [[False]*W for _ in range(H)]
    dq = deque([(Sx,Sy)])
    visited[Sx][Sy] = True
    while dq:
        x,y = dq.popleft()
        for dx_,dy_ in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny = x+dx_,y+dy_
            if 0<=nx<H and 0<=ny<W and not visited[nx][ny] and grid[nx][ny] != '#':
                visited[nx][ny] = True
                dq.append((nx,ny))
    canV = any(visited[i][j] and i+1<H and visited[i+1][j] for i in range(H) for j in range(W))
    canH = any(visited[i][j] and j+1<W and visited[i][j+1] for i in range(H) for j in range(W))

    MAXP = 20000
    is_prime = [True]*(MAXP+1)
    is_prime[0]=is_prime[1]=False
    for i in range(2,MAXP+1):
        if is_prime[i]:
            for j in range(i*i,MAXP+1,i):
                is_prime[j] = False

    def min_pad(base_big, base_small, delta, can_loop):
        if not can_loop:
            if base_big>=2 and base_small>=2 and is_prime[base_big] and is_prime[base_small]:
                return 0
            else:
                return None
        for t in range(0, MAXP - base_big +1):
            p = base_big + t
            q = p - delta
            if q < 2: continue
            if is_prime[p] and is_prime[q]:
                return t
        return None

    pad_v = min_pad(max(A0,B0), min(A0,B0), abs(dx), canV)
    pad_h = min_pad(max(C0,D0), min(C0,D0), abs(dy), canH)
    if pad_v is None or pad_h is None:
        print(-1)
        return

    ans = (A0 + B0 + C0 + D0) + 2*pad_v + 2*pad_h
    print(ans)

if __name__ == "__main__":
    solve()
0