問題概要
問題ページ
-
-
D - Wizard in Maze
問題ページへ移動する
問題文
縦 \(H\) マス、横 \(W\) マスの \(H\times W\) マスからなる迷路があります。
上から \(i\) 行目、左から \(j\) 列目のマス \((i,j)\) は、\(S_{ij}\) が # のとき壁であり、.のとき道です。
マス \((C_h,C_w)\) に魔法使いがいます。魔法使いは次の \(2\) 種類の方法で移動することができます。
- 移動A：現在いるマスと上下左右に隣接する道のマスへ歩いて移動する。
- 移動B：現在いるマスを中心とする \(5\times 5\) の範囲内にある道のマスへワープ魔法で移動する。
どちらの行動でも、迷路の外へ移動することはできません。
マス \((D_h,D_w)\) まで移動するには、ワープ魔法を最低で何度使う必要があるでしょうか。
制約
- \(1 \leq H,W \leq 10^3\)
- \(1 \leq C_h,D_h \leq H\)
- \(1 \leq C_w,D_w \leq W\)
- \(S_{ij}\) は
#か. - \(S_{C_h C_w}\) と \(S_{D_h D_w}\) は
. - \((C_h,C_w) \neq (D_h,D_w)\)
問題の考察
ACコード
import sys
import collections
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
h, w = list(map(int, input().rstrip('\n').split()))
ch, cw = list(map(int, input().rstrip('\n').split()))
dh, dw = list(map(int, input().rstrip('\n').split()))
hw = [[10 ** 10 if v == "." else -1 for v in list(str(input().rstrip('\n')))] for _ in range(h)]
cost_map = collections.defaultdict(list)
cost_map[0] = [[ch - 1, cw - 1]]
hw[ch -1][cw - 1] = 0
for i in range(10 ** 10):
ql = collections.deque()
if len(cost_map[i]) == 0:
print(-1)
exit()
for cost_x, cost_y in cost_map[i]:
ql.append([i, cost_x, cost_y])
while True:
if len(ql) != 0:
cost, xv, yv = ql.popleft()
if xv == dh - 1 and yv == dw - 1:
print(cost)
exit()
for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
if 0 <= xv < h and 0 <= yv < w:
if hw[xv][yv] == 10 ** 10:
ql.append([cost, xv, yv])
hw[xv][yv] = cost
cost_map[cost] += [[xv, yv]]
else:
break
ql = collections.deque()
for cost_x, cost_y in cost_map[i]:
ql.append([i, cost_x, cost_y])
while True:
if len(ql) != 0:
cost, xvn, yvn = ql.popleft()
for j in range(-2, 3):
for k in range(-2, 3):
for xv, yv in [[xvn + j, yvn + k]]:
if 0 <= xv < h and 0 <= yv < w:
if hw[xv][yv] != -1 and hw[xv][yv] == 10 ** 10:
hw[xv][yv] = i + 1
cost_map[i + 1] += [[xv, yv]]
else:
break
if __name__ == '__main__':
solve()