# 令和４年秋問３　迷路の探索
# =====================================================================
# 定数・変数の定義（表1に対応）
# =====================================================================
OK = 0         # OKフラグ
NG = 1         # NGフラグ（障害物・外壁）
VISITED = 2    # 足跡フラグ

# 大域変数として定義
maze = []          # 2次元配列 迷路図情報
start_x = 0        # 始点のx座標
start_y = 0        # 始点のy座標
goal_x = 0         # 終点のx座標
goal_y = 0         # 終点のy座標
stack_visit = []   # 経過を格納するスタック
stack_top = 0      # スタックポインタ
sol_num = 0        # 見つけた解の総数
paths = []         # 全ての解の座標を格納する2次元配列


# =====================================================================
# 図3：関数 visit(x, y) の実装
# =====================================================================
def visit(x, y):
    global stack_top, sol_num, maze, stack_visit, paths

    # マス情報に足跡フラグを入れる
    maze[x][y] = VISITED

    # スタックに座標を入れる
    # Pythonのリスト操作ですが、アルゴリズム通りstack_topの位置に代入します
    if len(stack_visit) <= stack_top:
        stack_visit.append((x, y))
    else:
        stack_visit[stack_top] = (x, y)

    # 終点に到達したかどうかの判定
    if (x == goal_x) and (y == goal_y):
        # pathsに現在の解を記録する（空欄 イ の処理）
        # paths[sol_num] の行（リスト）を用意してコピー
        current_path = []
        for k in range(0, stack_top + 1):
            current_path.append(stack_visit[k])
        paths.append(current_path)

        # 見つけた解の総数を増やす
        sol_num = sol_num + 1

    else:
        # スタックポインタを1ずつ増やす
        stack_top = stack_top + 1

        # ① y座標を1増やす（上）
        if maze[x][y+1] == OK:
            visit(x, y+1)

        # ② x座標を1増やす（右）
        if maze[x+1][y] == OK:
            visit(x+1, y)

        # ③ y座標を1減らす（下）
        if maze[x][y-1] == OK:
            visit(x, y-1)

        # ④ x座標を1減らす（左）
        if maze[x-1][y] == OK:
            visit(x-1, y)

        # 4方向いずれにも進めないとき、ポインタを戻す（空欄 ウ の処理）
        stack_top = stack_top - 1

    # 現在いるマスの情報をOKフラグに戻す（空欄 エ の処理）
    maze[x][y] = OK


# =====================================================================
# 図4：メインプログラム（main関数）の実装
# =====================================================================
def main():
    global stack_top, sol_num, maze, start_x, start_y, goal_x, goal_y, paths

    # 初期化
    stack_top = 0
    sol_num = 0
    paths = []

    # 始点と終点の座標を設定（図2：解が複数ある迷路の例）
    start_x, start_y = 1, 1
    goal_x, goal_y = 5, 5

    # 迷路図情報の設定（図2を再現。0が通路、1が外壁および障害物）
    # x座標, y座標の順で直感的に扱えるよう、縦横を反転させた2次元配列として用意しています。
    # 0行目と6行目、0列目と6列目はすべて外壁(NG)です。
    maze = [
        [NG, NG, NG, NG, NG, NG, NG], # x=0（外壁）
        [NG, OK, OK, OK, OK, OK, NG], # x=1（始点 (1,1) を含む列）
        [NG, OK, NG, OK, NG, OK, NG], # x=2（(2,2)と(2,4)が障害物）
        [NG, OK, OK, OK, OK, OK, NG], # x=3
        [NG, OK, OK, NG, OK, NG, NG], # x=4（(4,3)と(4,5)が障害物）
        [NG, OK, OK, OK, OK, OK, NG], # x=5（終点 (5,5) を含む列）
        [NG, NG, NG, NG, NG, NG, NG]  # x=6（外壁）
    ]

    # 探索を開始
    visit(start_x, start_y)

    # 結果の印字（空欄 オ の処理）
    if sol_num == 0:
        print("迷路の解は見つからなかった")
    else:
        # 見つかった解をすべて印字
        print(f"【解の総数】: {sol_num}個\n")
        for i, path in enumerate(paths):
            print(f"解 {i+1}:")
            print(" → ".join([f"({x},{y})" for x, y in path]))
            print("-" * 50)

# プログラムの実行
if __name__ == "__main__":
    main()