結果

問題 No.1323 うしらずSwap
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:47:38
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,954 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 625,152 KB
最終ジャッジ日時 2025-06-12 14:50:54
合計ジャッジ時間 7,385 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 MLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W, r_a, c_a, r_b, c_b = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        grid.append(list(sys.stdin.readline().strip()))
    
    start_a = (r_a - 1, c_a - 1)
    start_b = (r_b - 1, c_b - 1)
    target_a = start_b
    target_b = start_a

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    visited = dict()
    queue = deque()
    queue.append((start_a, start_b, 0))
    visited_key = (start_a[0], start_a[1], start_b[0], start_b[1])
    visited[visited_key] = 0

    found = False
    answer = -1

    while queue:
        a_pos, b_pos, steps = queue.popleft()

        if a_pos == target_a and b_pos == target_b:
            answer = steps
            found = True
            break

        a_r, a_c = a_pos
        b_r, b_c = b_pos

        for dr, dc in dirs:
            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_pos:
                    new_state = ((new_a_r, new_a_c), b_pos)
                    new_key = (new_a_r, new_a_c, b_r, b_c)
                    if new_key not in visited:
                        visited[new_key] = steps + 1
                        queue.append((new_state[0], new_state[1], steps + 1))

        for dr, dc in dirs:
            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_pos:
                    new_state = (a_pos, (new_b_r, new_b_c))
                    new_key = (a_r, a_c, new_b_r, new_b_c)
                    if new_key not in visited:
                        visited[new_key] = steps + 1
                        queue.append((new_state[0], new_state[1], steps + 1))

    print(answer if found else -1)

if __name__ == "__main__":
    main()
0