ABC 176 D Wizard in Maze【Python】

問題はこちら。

PyPyで。

// deque をインポート
from collections import deque

// いくつかの定数の設定
// 周囲 5 x 5 マスまで動けるので dh, dw は -2 から 2 まで
INF = 10**9
dh = [-2, -1, 0, 1, 2]
dw = [-2, -1, 0, 1, 2]

// 入力
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
board = [input() for _ in range(H)]

// 座標がずれているのでデクリメント
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

// デックとコストを記録する配列を用意
q = deque([])
cost = [[INF]*W for _ in range(H)]

// 初期化
q.append((Ch, Cw))
cost[Ch][Cw] = 0

// 探索開始
// 0-1 BFS
while q:
   // 左から pop
   h, w = q.popleft()
   for i in range(5):
       for j in range(5):
           // 次の候補地の座標を nh, nw とする
           nh, nw = h + dh[i], w + dw[j]
           dist = abs(dh[i]) + abs(dw[j])
           
           // フィールドから出たらスルー
           if nh < 0 or H <= nh or nw < 0 or W <= nw:
               continue
           
           // 壁だったらスルー
           if board[nh][nw] == '#':
               continue
           
           // 隣接している場合は cost = 0 で移動可能
           // 左に push
           if dist <= 1:
               if cost[nh][nw] > cost[h][w]:
                   cost[nh][nw] = cost[h][w]
                   q.appendleft((nh, nw))
           
           // 離れている場合は cost = 1 で移動可能
           // 右に push
           else:
               if cost[nh][nw] > cost[h][w] + 1:
                   cost[nh][nw] = cost[h][w] + 1
                   q.append((nh, nw))
                   
// (Dh, Dw) にたどり着くのに必要なコストが答え
ans = cost[Dh][Dw]

// 出力
print(ans if ans < INF else -1)