結果

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

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    H = int(data[idx]); idx +=1
    W = int(data[idx]); idx +=1
    r_a = int(data[idx]); idx +=1
    c_a = int(data[idx]); idx +=1
    r_b = int(data[idx]); idx +=1
    c_b = int(data[idx]); idx +=1
    
    grid = []
    for _ in range(H):
        grid.append(data[idx])
        idx +=1
    
    r_a -= 1
    c_a -= 1
    r_b -= 1
    c_b -= 1
    
    dirs = [ (-1,0), (1,0), (0,-1), (0,1) ]
    
    heap = []
    heapq.heappush(heap, (0, r_a, c_a, r_b, c_b))
    
    visited = dict()
    key = (r_a, c_a, r_b, c_b)
    visited[key] = 0
    
    target = (r_b, c_b, r_a, c_a)
    
    while heap:
        steps, a_r, a_c, b_r, b_c = heapq.heappop(heap)
        
        if (a_r, a_c) == (b_r, b_c):
            continue
        
        if (a_r, a_c, b_r, b_c) == target:
            print(steps)
            return
        
        if steps > visited.get( (a_r, a_c, b_r, b_c), float('inf') ):
            continue
        
        for move in [0, 1]:  # 0: move A, 1: move B
            if move == 0:
                for dr, dc in dirs:
                    na_r = a_r + dr
                    na_c = a_c + dc
                    if 0 <= na_r < H and 0 <= na_c < W:
                        if grid[na_r][na_c] == '.':
                            if na_r == b_r and na_c == b_c:
                                continue
                            new_state = (na_r, na_c, b_r, b_c)
                            new_steps = steps + 1
                            if new_state not in visited or new_steps < visited[new_state]:
                                visited[new_state] = new_steps
                                heapq.heappush(heap, (new_steps, na_r, na_c, b_r, b_c))
            else:
                for dr, dc in dirs:
                    nb_r = b_r + dr
                    nb_c = b_c + dc
                    if 0 <= nb_r < H and 0 <= nb_c < W:
                        if grid[nb_r][nb_c] == '.':
                            if nb_r == a_r and nb_c == a_c:
                                continue
                            new_state = (a_r, a_c, nb_r, nb_c)
                            new_steps = steps + 1
                            if new_state not in visited or new_steps < visited[new_state]:
                                visited[new_state] = new_steps
                                heapq.heappush(heap, (new_steps, a_r, a_c, nb_r, nb_c))
    
    print(-1)

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