結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)