ABC007 C – 幅優先探索｜かえるのほんだな

はじめに

競プロの精進のために学びがあった問題についてまとめています。目標は AtCoder 水色！

今のレートは茶色です。

問題

たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。
まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。

難易度は緑色。

考察

問題文に書いてあるとおり、幅優先探索を実装することで、効率的に迷路のゴールまでの最短経路を割り出すことができる。

シンプルな幅優先探索の実装で解けました。 2次配列の一つ目の要素がy軸になる点に注意。

コード

from collections import deque

R, C = map(int,input().split())
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())

NULL = -1
maze = []
for i in range(R):
    S = input()
    maze.append(S)

def check(y, x, d):
    if x == gx - 1 and y == gy - 1:
        print(d)
        exit()

que = deque([])
Seen = [[False for j in range(C)] for i in range(R)]
Dist = [[0 for j in range(C)] for i in range(R)]

ny, nx = sy-1, sx-1
que.append((ny, nx))
Seen[ny][nx] = True

while que:
    pop = que.popleft()
    ny, nx = pop[0], pop[1]

    if maze[ny-1][nx] == '.':
        if not Seen[ny-1][nx]:
            que.append((ny-1, nx))
            Dist[ny-1][nx] = Dist[ny][nx] + 1
            Seen[ny-1][nx] = True

            check(ny-1, nx, Dist[ny-1][nx])

    if maze[ny+1][nx] == '.':
        if not Seen[ny+1][nx]:
            que.append((ny+1, nx))
            Dist[ny+1][nx] = Dist[ny][nx] + 1
            Seen[ny+1][nx] = True

            check(ny+1, nx, Dist[ny+1][nx])

    if maze[ny][nx-1] == '.':
        if not Seen[ny][nx-1]:
            que.append((ny, nx-1))
            Dist[ny][nx-1] = Dist[ny][nx] + 1
            Seen[ny][nx-1] = True

            check(ny, nx-1, Dist[ny][nx-1])

    if maze[ny][nx+1] == '.':
        if not Seen[ny][nx+1]:
            que.append((ny, nx+1))
            Dist[ny][nx+1] = Dist[ny][nx] + 1
            Seen[ny][nx+1] = True

            check(ny, nx+1, Dist[ny][nx+1])