結果
問題 |
No.1323 うしらずSwap
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:57:00 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,062 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 82,212 KB |
実行使用メモリ | 528,108 KB |
最終ジャッジ日時 | 2025-06-12 19:57:40 |
合計ジャッジ時間 | 6,417 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 MLE * 1 -- * 45 |
ソースコード
import sys from collections import deque def main(): input = sys.stdin.read().split() ptr = 0 H = int(input[ptr]); ptr += 1 W = int(input[ptr]); ptr += 1 ra = int(input[ptr]); ptr += 1 ca = int(input[ptr]); ptr += 1 rb = int(input[ptr]); ptr += 1 cb = int(input[ptr]); ptr += 1 grid = [] for _ in range(H): row = input[ptr] grid.append(list(row)) ptr += 1 start_a = (ra-1, ca-1) start_b = (rb-1, cb-1) target_a = start_b target_b = start_a directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] visited = dict() queue = deque() initial_state = (start_a[0], start_a[1], start_b[0], start_b[1]) visited[initial_state] = 0 queue.append((start_a[0], start_a[1], start_b[0], start_b[1], 0)) found = False answer = -1 while queue: a_r, a_c, b_r, b_c, steps = queue.popleft() if (a_r, a_c) == target_a and (b_r, b_c) == target_b: answer = steps found = True break for dr, dc in directions: new_a_r = a_r + dr new_a_c = a_c + dc if 0 <= new_a_r < H and 0 <= new_a_c < W: if grid[new_a_r][new_a_c] == '.' and (new_a_r, new_a_c) != (b_r, b_c): new_state = (new_a_r, new_a_c, b_r, b_c) if new_state not in visited: visited[new_state] = steps + 1 queue.append((new_a_r, new_a_c, b_r, b_c, steps + 1)) for dr, dc in directions: new_b_r = b_r + dr new_b_c = b_c + dc if 0 <= new_b_r < H and 0 <= new_b_c < W: if grid[new_b_r][new_b_c] == '.' and (new_b_r, new_b_c) != (a_r, a_c): new_state = (a_r, a_c, new_b_r, new_b_c) if new_state not in visited: visited[new_state] = steps + 1 queue.append((a_r, a_c, new_b_r, new_b_c, steps + 1)) print(answer if found else -1) if __name__ == '__main__': main()