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)
この記事が気に入ったらサポートをしてみませんか?