結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-20 18:47:26 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,323 bytes |
コンパイル時間 | 516 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2025-04-20 18:47:29 |
合計ジャッジ時間 | 1,936 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 1 WA * 20 |
ソースコード
from collections import deque import sys def main() -> None: sys.setrecursionlimit(1 << 25) input_data = sys.stdin.read().rstrip().splitlines() it = iter(input_data) H, W = map(int, next(it).split()) Sy, Sx = map(int, next(it).split()) # 行, 列(1-indexed) Gy, Gx = map(int, next(it).split()) # 行, 列(1-indexed) Sy -= 1; Sx -= 1 Gy -= 1; Gx -= 1 grid = [list(next(it)) for _ in range(H)] DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)] MASKS = [1 << i for i in range(4)] INF = -1 dist = [[[INF] * 16 for _ in range(W)] for _ in range(H)] dq = deque() start_state = 0 dist[Sy][Sx][start_state] = 0 dq.append((Sy, Sx, start_state)) while dq: y, x, state = dq.popleft() d_now = dist[y][x][state] if (y, x) == (Gy, Gx) and state == 0: print(d_now) return for k, (dy, dx) in enumerate(DIRS): ny, nx = y + dy, x + dx if 0 <= ny < H and 0 <= nx < W and grid[ny][nx] != '#': nstate = state ^ MASKS[k] # 対応するビットを反転 if dist[ny][nx][nstate] == INF: dist[ny][nx][nstate] = d_now + 1 dq.append((ny, nx, nstate)) print(-1) if __name__ == "__main__": main()