結果
問題 |
No.1323 うしらずSwap
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:50:08 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,342 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 72,576 KB |
最終ジャッジ日時 | 2025-03-31 17:51:06 |
合計ジャッジ時間 | 7,567 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 TLE * 1 -- * 45 |
ソースコード
import sys from collections import deque def main(): H, W, r_a, c_a, r_b, c_b = map(int, sys.stdin.readline().split()) # Convert to 0-based indices r_a -= 1 c_a -= 1 r_b -= 1 c_b -= 1 grid = [] for _ in range(H): grid.append(sys.stdin.readline().strip()) # Target state: ushi at (r_b, c_b), hikari at (r_a, c_a) target = (r_b, c_b, r_a, c_a) # Visited dictionary: (u_r, u_c, h_r, h_c) -> steps visited = dict() # BFS queue elements: (u_r, u_c, h_r, h_c, steps) queue = deque() initial = (r_a, c_a, r_b, c_b, 0) queue.append(initial) visited_key = (r_a, c_a, r_b, c_b) visited[visited_key] = 0 # Directions: up, down, left, right dirs = [(-1,0), (1,0), (0,-1), (0,1)] found = False answer = -1 while queue: u_r, u_c, h_r, h_c, steps = queue.popleft() # Check if we've reached the target state if u_r == r_b and u_c == c_b and h_r == r_a and h_c == c_a: answer = steps found = True break # Generate next possible moves # First, try moving Ushisan for dr, dc in dirs: nu_r = u_r + dr nu_c = u_c + dc if 0 <= nu_r < H and 0 <= nu_c < W: if grid[nu_r][nu_c] == '.' and (nu_r, nu_c) != (h_r, h_c) and (nu_r, nu_c) != (h_r, h_c): # Check if this state is new or better new_key = (nu_r, nu_c, h_r, h_c) if new_key not in visited or steps + 1 < visited[new_key]: visited[new_key] = steps + 1 queue.append( (nu_r, nu_c, h_r, h_c, steps + 1) ) # Try moving Hikarichan for dr, dc in dirs: nh_r = h_r + dr nh_c = h_c + dc if 0 <= nh_r < H and 0 <= nh_c < W: if grid[nh_r][nh_c] == '.' and (nh_r, nh_c) != (u_r, u_c) and (nh_r, nh_c) != (u_r, u_c): new_key = (u_r, u_c, nh_r, nh_c) if new_key not in visited or steps + 1 < visited[new_key]: visited[new_key] = steps + 1 queue.append( (u_r, u_c, nh_r, nh_c, steps + 1) ) print(answer if found else -1) if __name__ == "__main__": main()