結果

問題 No.1323 うしらずSwap
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:56:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,988 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 426,520 KB
最終ジャッジ日時 2025-06-12 19:57:02
合計ジャッジ時間 6,469 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 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())
    
    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # BFS Initialization
    queue = deque()
    initial_state = (r_a - 1, c_a - 1, r_b - 1, c_b - 1)
    queue.append((initial_state[0], initial_state[1], initial_state[2], initial_state[3], 0))
    visited = set()
    visited.add((initial_state[0], initial_state[1], initial_state[2], initial_state[3]))
    
    target = (r_b - 1, c_b - 1, r_a - 1, c_a - 1)
    
    while queue:
        x1, y1, x2, y2, steps = queue.popleft()
        
        # Check if current state is the target
        if (x1, y1, x2, y2) == target:
            print(steps)
            return
        
        # Generate all possible moves for cow
        for dx, dy in directions:
            new_x1 = x1 + dx
            new_y1 = y1 + dy
            if 0 <= new_x1 < H and 0 <= new_y1 < W:
                if grid[new_x1][new_y1] != '#' and (new_x1, new_y1) != (x2, y2):
                    new_state = (new_x1, new_y1, x2, y2)
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append((new_x1, new_y1, x2, y2, steps + 1))
        
        # Generate all possible moves for girl
        for dx, dy in directions:
            new_x2 = x2 + dx
            new_y2 = y2 + dy
            if 0 <= new_x2 < H and 0 <= new_y2 < W:
                if grid[new_x2][new_y2] != '#' and (new_x2, new_y2) != (x1, y1):
                    new_state = (x1, y1, new_x2, new_y2)
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append((x1, y1, new_x2, new_y2, steps + 1))
    
    # If target is not reachable
    print(-1)

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