ABC176 D - Wizard in Maze - ペンギンかっこいい

備忘録

問題

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[INF] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    que = collections.deque()

    que.appendleft((Ch - 1, Cw - 1, 0))
    visited[Ch - 1][Cw - 1] = 0
    while que:
        h, w, c = que.popleft()
        for mh, mw in move:  # 移動A: 歩いて移動
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] > c:
                visited[ch][cw] = c
                que.appendleft((ch, cw, c))
        for wh in range(-2, 3):  # 移動B: ワープ魔法
            for ww in range(-2, 3):
                ch, cw = h + wh, w + ww
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] > c + 1:
                    visited[ch][cw] = c + 1
                    que.append((ch, cw, c + 1))

    ret = visited[Dh - 1][Dw - 1]
    print(-1 if ret == INF else ret)


if __name__ == '__main__':
    main()

考え方

上記のコードはPython (3.8.2)で提出を行ったらTLEだったため、
PyPy3 (7.3.0)で提出を行った。

BFS（深さ優先探索）を用いて、移動範囲を探索する。
歩いて移動できる範囲をコスト０で移動できるマス、
ワープ魔法で移動できる範囲をコスト１で移動できるマスと考え、
01-BFSを用いた回答を行う。

公式の解説通り、歩いて移動できる範囲をコスト０、ワープ魔法で移動できる範囲をコスト１と考えることで、
移動におけるコストが０と１だけなので、01-BFSで回答を行うことが出来る。
01-BFSの理解は以下の解説を読んだ。

01-BFSのちょっと丁寧な解説 - ARMERIA

簡単に言ってしまえば、両端キューを用意し、
移動コストが必要ない移動についてはキューの先頭に追加、
移動コストが必要な場合にはキューの末尾に追加する。
あとは先頭からキューを取り出し、再び移動範囲の探索を行なう。

実装は(h, w, (h,w)までの移動コスト)を持ったキューを用意し、
取り出したキューから歩いた場合と魔法で移動した場合の移動範囲を全て探索する。
なお、この時の探索は制約で与えられたグリッドの範囲内かつ、
移動コストを減少させることができる移動のみをキューに積んでいく。

追記:徒歩移動とワープ移動を別々のキューに持たせることで200msぐらい早くなった。
しかし、相変わらずPython (3.8.2)では通せない。。。
https://atcoder.jp/contests/abc176/submissions/16181571