結果

問題 No.1323 うしらずSwap
ユーザー gew1fw
提出日時 2025-06-12 19:07:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,235 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 72,320 KB
最終ジャッジ日時 2025-06-12 19:07:38
合計ジャッジ時間 6,984 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())
    ra -= 1
    ca -= 1
    rb -= 1
    cb -= 1
    grid = []
    for _ in range(H):
        grid.append(sys.stdin.readline().strip())
    
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def bfs(sr, sc, tr, tc):
        q = deque()
        visited = [[-1 for _ in range(W)] for _ in range(H)]
        q.append((sr, sc))
        visited[sr][sc] = 0
        while q:
            r, c = q.popleft()
            if r == tr and c == tc:
                return visited[r][c]
            for dr, dc in dirs:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] == '.' and visited[nr][nc] == -1:
                    visited[nr][nc] = visited[r][c] + 1
                    q.append((nr, nc))
        return -1
    
    dist_ushi = bfs(ra, ca, rb, cb)
    dist_hikari = bfs(rb, cb, ra, ca)
    
    if dist_ushi == -1 or dist_hikari == -1:
        print(-1)
        return
    
    q = deque()
    visited = dict()
    start = (ra, ca, rb, cb)
    q.append((ra, ca, rb, cb, 0))
    visited[start] = True
    found = False
    answer = -1
    
    target = (rb, cb, ra, ca)
    
    while q:
        ur, uc, hr, hc, steps = q.popleft()
        if (ur, uc, hr, hc) == target:
            answer = steps
            found = True
            break
        for d in dirs:
            nur = ur + d[0]
            nuc = uc + d[1]
            if 0 <= nur < H and 0 <= nuc < W and grid[nur][nuc] == '.' and (nur, nuc) != (hr, hc):
                state = (nur, nuc, hr, hc)
                if state not in visited:
                    visited[state] = True
                    q.append((nur, nuc, hr, hc, steps + 1))
        for d in dirs:
            nhr = hr + d[0]
            nhc = hc + d[1]
            if 0 <= nhr < H and 0 <= nhc < W and grid[nhr][nhc] == '.' and (nhr, nhc) != (ur, uc):
                state = (ur, uc, nhr, nhc)
                if state not in visited:
                    visited[state] = True
                    q.append((ur, uc, nhr, nhc, steps + 1))
    
    print(answer if found else -1)

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