結果

問題 No.1323 うしらずSwap
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:50:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,342 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 72,576 KB
最終ジャッジ日時 2025-03-31 17:51:06
合計ジャッジ時間 7,567 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())
    # Convert to 0-based indices
    r_a -= 1
    c_a -= 1
    r_b -= 1
    c_b -= 1
    grid = []
    for _ in range(H):
        grid.append(sys.stdin.readline().strip())
    
    # Target state: ushi at (r_b, c_b), hikari at (r_a, c_a)
    target = (r_b, c_b, r_a, c_a)
    
    # Visited dictionary: (u_r, u_c, h_r, h_c) -> steps
    visited = dict()
    
    # BFS queue elements: (u_r, u_c, h_r, h_c, steps)
    queue = deque()
    initial = (r_a, c_a, r_b, c_b, 0)
    queue.append(initial)
    visited_key = (r_a, c_a, r_b, c_b)
    visited[visited_key] = 0
    
    # Directions: up, down, left, right
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    
    found = False
    answer = -1
    
    while queue:
        u_r, u_c, h_r, h_c, steps = queue.popleft()
        
        # Check if we've reached the target state
        if u_r == r_b and u_c == c_b and h_r == r_a and h_c == c_a:
            answer = steps
            found = True
            break
        
        # Generate next possible moves
        # First, try moving Ushisan
        for dr, dc in dirs:
            nu_r = u_r + dr
            nu_c = u_c + dc
            if 0 <= nu_r < H and 0 <= nu_c < W:
                if grid[nu_r][nu_c] == '.' and (nu_r, nu_c) != (h_r, h_c) and (nu_r, nu_c) != (h_r, h_c):
                    # Check if this state is new or better
                    new_key = (nu_r, nu_c, h_r, h_c)
                    if new_key not in visited or steps + 1 < visited[new_key]:
                        visited[new_key] = steps + 1
                        queue.append( (nu_r, nu_c, h_r, h_c, steps + 1) )
        
        # Try moving Hikarichan
        for dr, dc in dirs:
            nh_r = h_r + dr
            nh_c = h_c + dc
            if 0 <= nh_r < H and 0 <= nh_c < W:
                if grid[nh_r][nh_c] == '.' and (nh_r, nh_c) != (u_r, u_c) and (nh_r, nh_c) != (u_r, u_c):
                    new_key = (u_r, u_c, nh_r, nh_c)
                    if new_key not in visited or steps + 1 < visited[new_key]:
                        visited[new_key] = steps + 1
                        queue.append( (u_r, u_c, nh_r, nh_c, steps + 1) )
    
    print(answer if found else -1)

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