Edit

【pythonでABC176を解説】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()

-Edit
-