結果

問題 No.1323 うしらずSwap
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:26:20
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,126 bytes
コンパイル時間 428 ms
コンパイル使用メモリ 81,592 KB
実行使用メモリ 533,444 KB
最終ジャッジ日時 2025-04-16 00:27:49
合計ジャッジ時間 6,668 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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(sys.stdin.readline().strip())
    
    # Convert to 0-based indices
    u_start = (r_a - 1, c_a - 1)
    h_start = (r_b - 1, c_b - 1)
    target_u = h_start
    target_h = u_start

    # Check if already at target
    if u_start == target_u and h_start == target_h:
        print(0)
        return

    # Directions: up, down, left, right
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # BFS queue: (u_pos, h_pos, steps)
    queue = deque()
    queue.append((u_start, h_start, 0))
    visited = set()
    visited.add((u_start[0], u_start[1], h_start[0], h_start[1]))

    found = False

    while queue:
        u_pos, h_pos, steps = queue.popleft()

        # Check if current state is target
        if u_pos == target_u and h_pos == target_h:
            print(steps)
            found = True
            break

        # Generate moves for Ushi
        for dr, dc in dirs:
            new_r = u_pos[0] + dr
            new_c = u_pos[1] + dc
            if 0 <= new_r < H and 0 <= new_c < W:
                if grid[new_r][new_c] == '.' and (new_r, new_c) != h_pos:
                    new_u = (new_r, new_c)
                    new_state = (new_r, new_c, h_pos[0], h_pos[1])
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append((new_u, h_pos, steps + 1))

        # Generate moves for Hikari
        for dr, dc in dirs:
            new_r = h_pos[0] + dr
            new_c = h_pos[1] + dc
            if 0 <= new_r < H and 0 <= new_c < W:
                if grid[new_r][new_c] == '.' and (new_r, new_c) != u_pos:
                    new_h = (new_r, new_c)
                    new_state = (u_pos[0], u_pos[1], new_r, new_c)
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append((u_pos, new_h, steps + 1))

    if not found:
        print(-1)

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