結果

問題 No.1323 うしらずSwap
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:50:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,768 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 439,000 KB
最終ジャッジ日時 2025-03-26 15:50:58
合計ジャッジ時間 6,958 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())
    grid = []
    for _ in range(H):
        grid.append(list(sys.stdin.readline().strip()))
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    start_ushi = (ra-1, ca-1)
    start_hikari = (rb-1, cb-1)
    target_ushi = (rb-1, cb-1)
    target_hikari = (ra-1, ca-1)
    
    visited = dict()
    q = deque()
    q.append((start_ushi[0], start_ushi[1], start_hikari[0], start_hikari[1], 0))
    visited[(start_ushi[0], start_ushi[1], start_hikari[0], start_hikari[1])] = 0
    
    answer = -1
    while q:
        ur, uc, hr, hc, steps = q.popleft()
        
        if (ur, uc) == target_ushi and (hr, hc) == target_hikari:
            answer = steps
            break
        
        for dr, dc in directions:
            nur = ur + dr
            nuc = uc + dc
            if 0 <= nur < H and 0 <= nuc < W:
                if grid[nur][nuc] == '.' and (nur, nuc) != (hr, hc):
                    if (nur, nuc, hr, hc) not in visited or visited[(nur, nuc, hr, hc)] > steps + 1:
                        visited[(nur, nuc, hr, hc)] = steps + 1
                        q.append((nur, nuc, hr, hc, steps + 1))
        
        for dr, dc in directions:
            nhr = hr + dr
            nhc = hc + dc
            if 0 <= nhr < H and 0 <= nhc < W:
                if grid[nhr][nhc] == '.' and (nhr, nhc) != (ur, uc):
                    if (ur, uc, nhr, nhc) not in visited or visited[(ur, uc, nhr, nhc)] > steps + 1:
                        visited[(ur, uc, nhr, nhc)] = steps + 1
                        q.append((ur, uc, nhr, nhc, steps + 1))
    
    print(answer if answer != -1 else -1)

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