結果

問題 No.1323 うしらずSwap
ユーザー lam6er
提出日時 2025-04-16 00:23:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,135 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 71,428 KB
最終ジャッジ日時 2025-04-16 00:24:48
合計ジャッジ時間 6,700 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())
    grid = []
    for _ in range(H):
        grid.append(sys.stdin.readline().strip())
    
    # 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, moves)
    q = deque()
    visited = dict()

    start_state = (ra, ca, rb, cb)
    q.append((ra, ca, rb, cb, 0))
    visited[start_state] = 0

    answer = -1

    while q:
        ur, uc, hr, hc, moves = q.popleft()

        # Check if both are at their target positions
        if ur == rb and uc == cb and hr == ra and hc == ca:
            answer = moves
            break

        # Generate possible moves
        # Either Ushi moves or Hikari moves
        # First, try moving Ushi
        for dr, dc in dirs:
            nur = ur + dr
            nuc = uc + dc
            # Check boundaries and obstacle
            if 0 <= nur < H and 0 <= nuc < W and grid[nur][nuc] == '.':
                # Check if the new position is not occupied by Hikari
                if (nur, nuc) != (hr, hc):
                    new_state = (nur, nuc, hr, hc)
                    if new_state not in visited or visited[new_state] > moves + 1:
                        visited[new_state] = moves + 1
                        q.append((nur, nuc, hr, hc, moves + 1))

        # Then, try moving Hikari
        for dr, dc in dirs:
            nhr = hr + dr
            nhc = hc + dc
            # Check boundaries and obstacle
            if 0 <= nhr < H and 0 <= nhc < W and grid[nhr][nhc] == '.':
                # Check if the new position is not occupied by Ushi
                if (nhr, nhc) != (ur, uc):
                    new_state = (ur, uc, nhr, nhc)
                    if new_state not in visited or visited[new_state] > moves + 1:
                        visited[new_state] = moves + 1
                        q.append((ur, uc, nhr, nhc, moves + 1))

    print(answer)

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