結果

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

ソースコード

diff # 

from collections import deque
import sys

# --- 入力 ---
H, W = map(int, sys.stdin.readline().split())
Sx, Sy = map(int, sys.stdin.readline().split())
Gx, Gy = map(int, sys.stdin.readline().split())
grid = [list(sys.stdin.readline().rstrip()) for _ in range(H)]

# 0‑indexed へ
Sx -= 1; Sy -= 1
Gx -= 1; Gy -= 1

dirs = [
    (1, 0, 0),   # A  ↓,  bit0
    (-1, 0, 1),  # B  ↑,  bit1
    (0, 1, 2),   # C  →,  bit2
    (0, -1, 3),  # D  ←,  bit3
]

INF = 10**9
dist = [[[INF]*16 for _ in range(W)] for _ in range(H)]
q = deque()

start_mask = 0  # どの操作回数も 0 (偶数)
dist[Sx][Sy][start_mask] = 0
q.append((Sx, Sy, start_mask))

while q:
    x, y, m = q.popleft()
    d = dist[x][y][m]
    if (x, y) == (Gx, Gy) and m == 0:
        print(d)
        sys.exit(0)

    for dx, dy, bit in dirs:
        nx, ny = x+dx, y+dy
        if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] != '#':
            nm = m ^ (1 << bit)          # 対応するビットを反転
            if dist[nx][ny][nm] == INF:
                dist[nx][ny][nm] = d + 1
                q.append((nx, ny, nm))

# 到達不可
print(-1)
0