くろたんく雑記帳

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

MENU

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

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

実行時間ギリギリ

以前の参考問題

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

blacktanktop.hatenablog.com

概要

問題

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

解くときに考えた内容

  • 迷路を{\displaystyle .}を-1、{\displaystyle \#}を-2とする。
  • 迷路をBFSで解こうとする。 (visitedでワープ回数を管理)
  • 移動A→移動しきったら→移動Bの繰り返し。
  • 実装上の注意は以下。
    • 移動Aで移動した場所をリストで持つ(ワープするスタート地点にしたいから)
    • 移動Aの時は、「今まで行ったことがない場所への移動の時は」直前のvisitedの値(これまでのワープの回数)をそのまま代入(ワープの回数が主題なので)
    • 移動Bの時は、「今まで行ったことがない場所への移動の時は」直前のvisitedの値(これまでのワープの回数)+1を代入(ワープをしているので)
    • さらに、これだけではダメで、迷路の外側に{\displaystyle \#\#}で包む。({\displaystyle 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

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()

書籍

最近ポチった書籍
  • 実用的でないPythonプログラミング

バカ売れしているのか、アマゾンでは値段があがっている。自分は、予約していたのに来ないので、楽天で購入した。 内容としては、面白いテーマの物が多く、pygletなどを使って描画もあるような内容が結構推されているが、アルゴリズムに関する内容もある。特に前半は文字列を操作して暗号解読であったり、アナグラム・回文といったものが扱われているので勉強になる。遺伝的アルゴリズムも面白く金庫破りの実装は非常に参考になった。

blacktanktop.hatenablog.com

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。(というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので)
投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本(ソフトカバー)

drken1215.hatenablog.com

アルゴリズムの参考書籍

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