Python3で解く AtCoder Beginner Contest 176 D - Wizard in Maze

上下左右の移動だけでなく、制限があるワープができる条件で、最低限のワープ数で迷路にゴールできるかを問う問題。結論から言うと、計算量的にきつかった。自分にはこれ以上は思いつかなかったが、ともかく、普通の移動→そこをスタート地点してワープ→そこをスタート地点にして普通の移動の繰り返しを行うようにした。

実行時間ギリギリ

やっと通った。
1903ms

読み込み高速化（input = sys.stdin.readline）と、
初期設定で'##'で迷路を囲めばBFS内の無駄なif文を回避。この処理はindexのこと考えなくていいだけでなく、スピードも早まるのかとやっと理解した
結構鬼というか、ギリギリいける設定が逆にすごいhttps://t.co/msy6RhwOio
— くろたんく@激しく多忙 (@black_tank_top) 2020年8月24日

以前の参考問題
概要
解くときに考えた内容
コード
- TLE
- AC
書籍
- 最近ポチった書籍
- アルゴリズムの参考書籍

以前の参考問題

迷路問題といえば、最大手数がかかるスタートとゴールの設定をすると言う問題があったが、それよりも色んな意味で大変だった。

blacktanktop.hatenablog.com

概要

問題

$h$ x $w$ の迷路がある。
上から $i$ 行目、左から $j$ 列目のマス、 $S_{ij}$ が $\#$ のとき壁であり通れず、 $.$ のとき道であり通れる。
スタートは $(C_h, C_w)$ 。
ゴールは $(D_h, D_w)$ 。
移動は以下の2種類。
1. 移動A：現在いるマスと上下左右に隣接する道のマスへ歩いて移動する。
2. 移動B：現在いるマスを中心とする 5×5の範囲内にある道のマスへワープ魔法で移動する。
どちらの行動でも、迷路の外へ移動することはできない。
ゴールまで移動するには、ワープ魔法を最低で何度使う必要があるか？

解くときに考えた内容

迷路を $.$ を-1、 $\#$ を-2とする。
迷路をBFSで解こうとする。 (visitedでワープ回数を管理)
移動A→移動しきったら→移動Bの繰り返し。
実装上の注意は以下。
- 移動Aで移動した場所をリストで持つ（ワープするスタート地点にしたいから）
- 移動Aの時は、「今まで行ったことがない場所への移動の時は」直前のvisitedの値（これまでのワープの回数）をそのまま代入（ワープの回数が主題なので）
- 移動Bの時は、「今まで行ったことがない場所への移動の時は」直前のvisitedの値（これまでのワープの回数）+1を代入（ワープをしているので）
- さらに、これだけではダメで、迷路の外側に $\#\#$ で包む。（ $0 \leq 次の移動先 \leq h, w$ とする条件分岐の計算をさせないため。この処理をしておけば、次のif文では-1かどうかしか見ていないし、out of indexにもならない）
- あとはinputもinput = sys.stdin.readlineとして高速化を意図した。

f:id:black_tank_top:20200825065214j:plain — 移動Aして移動Bして移動Aしてというときのvisitedのイメージ（今回はvisitedは移動Bの数）

コードのコメントアウトにある程度詳しく書いた。

コード

TLE

これでダメとなると、ちょいと微妙。。。
あとはどこの処理を軽くしてあげれば良いのやら。。。https://t.co/YJ1yrAgGHU #atcoder
— くろたんく@激しく多忙 (@black_tank_top) 2020年8月24日

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh, dw = map(int, input().split())
dh -= 1
dw -= 1
maze = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            visited[i][j] = -2
visited[ch][cw] = 0
walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
telpo = [[i,j] for i in range(-2, 3) for j in range(-2, 3)]
q_walk = deque([[ch, cw]])
q_telpo = deque([])
while q_walk:
    yw, xw = q_walk.popleft()
    # 行った場所を管理
    q_telpo.append([yw, xw])
    for i, j in walk:
        ny, nx = yw + i, xw + j
        # ここの条件分岐は改善の余地あり
        if ny < 0 or h <= ny or nx < 0 or w <= nx:
            continue
        if visited[ny][nx] == -1:
            # 行ったことがなければワープ回数を代入
            visited[ny][nx] = visited[yw][xw]
            q_walk.append([ny, nx])
    # 歩ける場所なくなったらワープ
    if len(q_walk) == 0:
        while q_telpo:
            yt, xt = q_telpo.popleft()
            for i, j in telpo:
                my, mx = yt + i, xt + j
                # ここの条件分岐は改善の余地あり
                if my < 0 or h <= my or mx < 0 or w <= mx:
                    continue
                if visited[my][mx] == -1:
                    # 行ったことがなければワープ回数に+1した値を代入
                    visited[my][mx] = visited[yt][xt] + 1
                    q_walk.append([my, mx])
print(visited[dh][dw])

AC

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    # 迷路の四方を##で囲む。
    # 移動で枠外にでてしまってindexがないことを阻止するための
    # if文を回避
    maze = ['#' * (w+4)]
    maze.append('#' * (w+4))
    for _ in range(h):
        maze.append('##' + input()[:-1] + '##')
    maze.append('#' * (w+4))
    maze.append('#' * (w+4))
    visited = [[-1] * (w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if maze[i][j] == '#':
                visited[i][j] = -2
    # この条件ではindexを+1しないとダメ
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    visited[ch][cw] = 0
    walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    telepo = [[i,j] for i in range(-2, 3) for j in range(-2, 3)]

    q_walk = deque([[ch, cw]])
    q_telepo = deque([])
    while q_walk:
        yw, xw = q_walk.popleft()
        # 行った場所を管理
        q_telepo.append([yw, xw])
        for i, j in walk:
            ny, nx = yw + i, xw + j
            # if ny < 0 or h <= ny or nx < 0 or w <= nx:
            #     continue
            if visited[ny][nx] == -1:
                # 行ったことがなければワープ回数を代入
                visited[ny][nx] = visited[yw][xw]
                q_walk.append([ny, nx])
        # 歩ける場所なくなったらワープ
        if len(q_walk) == 0:
            while q_telepo:
                yt, xt = q_telepo.popleft()
                for i, j in telepo:
                    my, mx = yt + i, xt + j
                    # if my < 0 or h <= my or mx < 0 or w <= mx:
                    #     continue
                    # 次がまだ行ったことないところだったら、今までのワープ回数+1
                    # つまり、テレポートしないといけない場所
                    if visited[my][mx] == -1:
                        visited[my][mx] = visited[yt][xt] + 1
                        q_walk.append([my, mx])
    print(visited[dh][dw])

if __name__ == '__main__':
    main()

書籍

アルゴリズムの参考書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい）ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者:渡部有隆
発売日: 2015/01/30
メディア: Kindle版

くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

Python3で解く AtCoder Beginner Contest 176 D - Wizard in Maze

以前の参考問題

概要

解くときに考えた内容

コード

TLE

AC

書籍

最近ポチった書籍

アルゴリズムの参考書籍