幅優先探索の練習

幅優先探索(BFS)の練習としてatCoderの問題を解いた
問題は「第三回アルゴリズム実技検定」のG問題「グリッド金移動」
(https://atcoder.jp/contests/past202005-open/tasks/past202005_g)

問題の把握

移動法に癖がある最短経路探索の問題

グラフとして考えると、グリッドのサイズをKとして、頂点の数K²で、辺の数はせいぜい 8K。
BFSは頂点の数をN、辺の数をMとして、計算量が O(N + M) 。
よって今回は頂点数が支配的になりO(K²)

題意から障害物とゴールの座標の外側である
-201 <= x <= 201, -201 <= y <= 201
を考えればよく、403 * 403 の二次元配列を考えればいい。

pythonの計算回数の目安は10**7くらいらしいので、余裕をもってクリアしている。

実装

シンプルに実装する

from collections import deque


N, X, Y = list(map(int, input().split()))


# 定数
gsize = 403
st_index = 201


# 座標を配列のインデックスに合わせる
X += st_index
Y += st_index


# 迷路を表す配列(Falseで初期化)
S = []
for i in range(gsize):
    S.append([False] * gsize)


# 障害物のマスをTrueにする
for i in range(N):
    x, y = list(map(int, input().split()))
    # 座標を配列のインデックスに合わせる
    x += st_index
    y += st_index
    S[x][y] = True


# 距離管理用の配列（-1で初期化）
dist = []
for i in range(gsize):
    dist.append([-1] * gsize)


Q = deque()
# 原点の距離を0で更新してキュー
dist[st_index][st_index] = 0
Q.append([st_index, st_index])


while len(Q) > 0:
    i, j = Q.popleft()


    # 6方向を確認する
    for i2, j2 in [
        [i + 1, j + 1],
        [i, j + 1],
        [i - 1, j + 1],
        [i + 1, j],
        [i - 1, j],
        [i, j - 1],
    ]:
        # インデックス外は無視
        if not (0 <= i2 <= gsize - 1 and 0 <= j2 <= gsize - 1):
            continue
        # 障害物は無視
        if S[i2][j2]:
            continue
        # 未訪問なら距離を更新してキュー
        if dist[i2][j2] == -1:
            dist[i2][j2] = dist[i][j] + 1
            Q.append([i2, j2])


# 距離を出力
print(dist[X][Y])

ACできた。pypyだと3倍くらい速かったのでpypyで提出するのがよさそう。

まとめ

テキスト通りの実装ができた。何日か連続して解いて手に覚えさせたい。