# 1 がゴール
maze = [
    [9, 9, 9, 9, 9, 9, 9, 9, 9],
    [9, 0, 0, 0, 9, 9, 0, 9, 9],
    [9, 0, 9, 9, 0, 0, 0, 0, 9],
    [9, 0, 0, 0, 0, 9, 9, 9, 9],
    [9, 9, 0, 9, 0, 9, 0, 1, 9],
    [9, 0, 0, 9, 0, 0, 0, 9, 9],
    [9, 0, 9, 0, 0, 9, 0, 0, 9],
    [9, 9, 9, 9, 9, 9, 9, 9, 9],
]

d = [[0, -1], [-1, 0], [0, 1], [1, 0]]

# 探索済みのログ
log = [[1, 1]]

# キュー(x座標、y座標、深さのリスト)
queue = [[1, 1, 0]]

while len(queue) > 0:
    # キューの先頭を取り出し
    x, y, depth = queue.pop(0)

    for move in d:
        xd, yd = x + move[0], y + move[1]

        if maze[xd][yd] == 1:
            # ゴールしたら距離を出力して終了
            print(depth + 1)  # 現在の深さをインクリメント
            exit
        elif maze[xd][yd] != 9:
            if [xd, yd] not in log:
                # 過去に移動していない場所の場合、ログとキューに追加する
                log.append([xd, yd])
                # 現在の深さをインクリメントして追加
                queue.append([xd, yd, depth + 1])
