結果
問題 |
No.1323 うしらずSwap
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:56:32 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,534 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 290,852 KB |
最終ジャッジ日時 | 2025-06-12 19:57:18 |
合計ジャッジ時間 | 6,654 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 TLE * 1 -- * 45 |
ソースコード
import heapq def main(): import sys input = sys.stdin.read data = input().split() idx = 0 H = int(data[idx]); idx +=1 W = int(data[idx]); idx +=1 r_a = int(data[idx]); idx +=1 c_a = int(data[idx]); idx +=1 r_b = int(data[idx]); idx +=1 c_b = int(data[idx]); idx +=1 grid = [] for _ in range(H): grid.append(data[idx]) idx +=1 r_a -= 1 c_a -= 1 r_b -= 1 c_b -= 1 dirs = [ (-1,0), (1,0), (0,-1), (0,1) ] heap = [] heapq.heappush(heap, (0, r_a, c_a, r_b, c_b)) visited = dict() key = (r_a, c_a, r_b, c_b) visited[key] = 0 target = (r_b, c_b, r_a, c_a) while heap: steps, a_r, a_c, b_r, b_c = heapq.heappop(heap) if (a_r, a_c) == (b_r, b_c): continue if (a_r, a_c, b_r, b_c) == target: print(steps) return if steps > visited.get( (a_r, a_c, b_r, b_c), float('inf') ): continue for move in [0, 1]: # 0: move A, 1: move B if move == 0: for dr, dc in dirs: na_r = a_r + dr na_c = a_c + dc if 0 <= na_r < H and 0 <= na_c < W: if grid[na_r][na_c] == '.': if na_r == b_r and na_c == b_c: continue new_state = (na_r, na_c, b_r, b_c) new_steps = steps + 1 if new_state not in visited or new_steps < visited[new_state]: visited[new_state] = new_steps heapq.heappush(heap, (new_steps, na_r, na_c, b_r, b_c)) else: for dr, dc in dirs: nb_r = b_r + dr nb_c = b_c + dc if 0 <= nb_r < H and 0 <= nb_c < W: if grid[nb_r][nb_c] == '.': if nb_r == a_r and nb_c == a_c: continue new_state = (a_r, a_c, nb_r, nb_c) new_steps = steps + 1 if new_state not in visited or new_steps < visited[new_state]: visited[new_state] = new_steps heapq.heappush(heap, (new_steps, a_r, a_c, nb_r, nb_c)) print(-1) if __name__ == "__main__": main()