【AtCoder版！蟻本】ABC 007 C - 幅優先探索【幅優先探索】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210317152559p:plain
AtCoder版！蟻本の幅優先探索で類題としてあげられているABC007 CをPythonで解いていきます。
深さ優先探索と似ている部分もあり、あわせて学習すると理解しやすかったです。

リンク

atcoder.jp

AtCoder Beginner Contest 007 C - 幅優先探索

問題文

たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。

まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。
今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。

制約

・1 行目には、行数 R(1≦R≦50)と列数 C(1≦C≦50)がそれぞれ空白区切りで与えられる。
・2 行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。スタート地点が sy 行 sx 列にあることを意味する。 1≦sy≦R　かつ 1≦sx≦C である。
・3 行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。ゴール地点が gy 行 gx 列にあることを意味する。 1≦gy≦R　かつ 1≦gx≦C であり、(gy,gx)≠(sy,sx)であることが保障されている。
・4 行目から R 行、長さ C の文字列が 1 行ずつ与えられる。各文字は . もしくは # のいずれかであり、i 回目 (1≦i≦R) に与えられられる文字列のうち j 文字目 (1≦j≦C) について、その文字が . なら、マス (i,j) が空きマスであり、# なら、マス (i,j) が壁マスであることをあらわす。
・盤面は壁マスで囲まれている。つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス (i,j) について、c(i,j) は #である。また、スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。

解答例

from collections import deque

INF = int(1e9)

r, c = map(int,input().split())
sy, sx = map(int,input().split())
sy -= 1
sx -= 1
gy, gx = map(int,input().split())
gy -= 1
gx -= 1

maze = [] # 迷路の文字配列
for i in range(r):
    maze.append(input())

# 各座標への最短距離の配列（INFで初期化）
D = [[INF] * c for _ in range(r)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# スタートからゴールへの最短距離を求めるbfs
def bfs():
    que = deque()
    que.append([sy,sx])   # スタート地点をキューに入れる
    D[sy][sx] = 0       # スタート地点の距離を0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.popleft()   # 先入れのキューの要素を取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4):  # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            # 移動可能か、訪れたことがあるかの判定
            if 0 <= nx < c and 0 <= ny < r and maze[ny][nx] != "#" and D[ny][nx] == INF:
                # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する
                que.append([ny,nx])
                D[ny][nx] = D[p[0]][p[1]] + 1
    return D[gy][gx]

print(bfs())

解説

R行C列の迷路においてスタート地点からゴール地点への最短距離を求める問題です。

以前に記事にした深さ優先探索の問題と似ています。
ebisuke33.hatenablog.com

深さ優先探索との違いはキューに入れた順番（popleft）で探索している点です。

先入れ先出しで探索し、最短距離のリストDを更新していきます。
ゴールに到着したら探索を終了し、ゴールまでの最短距離を出力すればOKです。

深さ優先探索のあとだったので理解しやすくて助かりました。
迷路探索のような問題に有効なのでしっかり覚えていきたいです。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク