結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W, ra, ca, rb, cb = map(int, sys.stdin.readline().split())
    S = [sys.stdin.readline().strip() for _ in range(H)]
    
    # Convert to 0-based indices
    ra -= 1
    ca -= 1
    rb -= 1
    cb -= 1
    
    # Directions: up, down, left, right
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # BFS queue: (ushi_r, ushi_c, hikari_r, hikari_c, steps)
    q = deque()
    initial_state = (ra, ca, rb, cb)
    q.append((ra, ca, rb, cb, 0))
    
    visited = {}
    visited_key = (ra, ca, rb, cb)
    visited[visited_key] = 0
    
    found = False
    while q:
        ur, uc, hr, hc, steps = q.popleft()
        
        # Check if the current state is the target
        if ur == rb and uc == cb and hr == ra and hc == ca:
            print(steps)
            found = True
            break
        
        # Generate next states by moving Ushi
        for dr, dc in dirs:
            nur = ur + dr
            nuc = uc + dc
            if 0 <= nur < H and 0 <= nuc < W:
                if S[nur][nuc] == '.' and (nur != hr or nuc != hc):
                    new_state = (nur, nuc, hr, hc)
                    key = new_state
                    if key not in visited or steps + 1 < visited.get(key, float('inf')):
                        visited[key] = steps + 1
                        q.append((nur, nuc, hr, hc, steps + 1))
        
        # Generate next states by moving Hikari
        for dr, dc in dirs:
            nhr = hr + dr
            nhc = hc + dc
            if 0 <= nhr < H and 0 <= nhc < W:
                if S[nhr][nhc] == '.' and (nhr != ur or nhc != uc):
                    new_state = (ur, uc, nhr, nhc)
                    key = new_state
                    if key not in visited or steps + 1 < visited.get(key, float('inf')):
                        visited[key] = steps + 1
                        q.append((ur, uc, nhr, nhc, steps + 1))
    
    if not found:
        print(-1)

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