結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W, ra, ca, rb, cb = map(int, sys.stdin.readline().split())
    ra -= 1
    ca -= 1
    rb -= 1
    cb -= 1
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append(line)
    
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    target_a = (rb, cb)
    target_b = (ra, ca)
    
    initial_state = (ra, ca, rb, cb)
    target_state = (rb, cb, ra, ca)
    
    visited = {}
    queue = deque()
    queue.append((initial_state[0], initial_state[1], initial_state[2], initial_state[3], 0))
    visited[(initial_state[0], initial_state[1], initial_state[2], initial_state[3])] = True
    
    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 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_r, b_c):
                    if (new_a_r, new_a_c, b_r, b_c) not in visited:
                        visited[(new_a_r, new_a_c, b_r, b_c)] = True
                        queue.append((new_a_r, new_a_c, b_r, b_c, 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_r, a_c):
                    if (a_r, a_c, new_b_r, new_b_c) not in visited:
                        visited[(a_r, a_c, new_b_r, new_b_c)] = True
                        queue.append((a_r, a_c, new_b_r, new_b_c, steps + 1))
    
    print(answer)

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