令和4年度 秋期 応用情報技術者試験 午後 問3 再帰とスタックによる迷路探索のトレース

迷路の探索処理に関する次の記述を読んで，設問に答えよ。

始点と終点を任意の場所に設定する $n imes m$ の 2次元のマスの並びから成る迷路の解を求める問題を考える。本問の迷路では次の条件で解を見つける。

• 迷路内には障害物のマスがあり，$n imes m$ のマスを囲む外壁のマスがある。障害物と外壁のマスを通ることはできない。
• 任意のマスから，そのマスに隣接し，通ることのできるマスに移動できる。迷路の解とは，この移動の繰返しで始点から終点にたどり着くまでのマスの並びである。ただし，迷路の解では同じマスを 2回以上通ることはできない。
• 始点と終点は異なるマスに設定されている。

$5 imes 5$ の迷路の例を示す。解が一つの迷路の例を図1に，解が複数（四つ）ある迷路の例を図2に示す。

〔迷路の解を見つける探索〕

迷路の解を全て見つける探索の方法を次のように考える。

迷路と外壁の各マスの位置を x座標と y座標で表し，各マスについてそのマスに関する情報（以下，マス情報という）を考える。与えられた迷路に対して，障害物と外壁のマス情報には NGフラグを，それ以外のマス情報には OKフラグをそれぞれ設定する。マス情報全体を迷路図情報という。

探索する際の“移動”には，“進む”と“戻る”の二つの動作がある。“進む”は，現在いるマスから① y座標を1増やす，② x座標を1増やす，③ y座標を1減らす，④ x座標を1減らす，のいずれかの方向に動くことである。マスに“進む”と同時にそのマスのマス情報に足跡フラグを入れる。足跡フラグが入ったマスには“進む”ことはできない。“戻る”は，今いるマスから“進んで”きた一つ前のマスに動くことである。マスに“移動”したとき，移動先のマスを“訪問”したという。

探索は，始点のマスのマス情報に足跡フラグを入れ，始点のマスを“訪問”したマスとして，始点のマスから開始する。現在いるマスから次のマスに“進む”試みを①〜④の順に行い，もし試みた方向のマスに“進む”ことができないならば，次の方向に“進む”ことを試みる。4方向いずれにも“進む”ことができないときには，現在いるマスのマス情報をOKフラグに戻し，一つ前のマスに“戻る”。これを終点に到達するまで繰り返す。終点に到達したとき，始点から終点まで“進む”ことでたどってきたマスの並びが迷路の解の一つとなる。

迷路の解を見つけた後も，他の解を見つけるために，終点から一つ前のマスに“戻り”，迷路の探索を続け，全ての探索を行ったら終了する。迷路を探索している間，それまでの経過をスタックに格納しておく。終点にたどり着いた時点でスタックの内容を順番にたどると，それが解の一つになる。

図1の迷路では，始点から始めて，(1, 1)→(1, 2)→(1, 3)→(1, 4)→(1, 5)→(2, 5)→(1, 5)→(1, 4)のように“移動”する。ここまででマスの“移動”は7回起きていて，このときスタックには経過を示す4個の座標が格納されている。さらに探索を続けて，始めから13回目の“移動”が終了した時点では，スタックには ア 個の座標が格納されている。

〔迷路の解を全て求めて表示するプログラム〕

迷路の解を全て求めて表示するプログラムを考える。プログラム中で使用する主な変数，定数及び配列を表1に示す。配列の添字は全て0から始まり，要素の初期値は全て0とする。迷路を探索してマスを“移動”する関数 visitのプログラムを図3に，メインプログラムを図4に示す。メインプログラム中の変数及び配列は大域変数とする。

〔解が複数ある迷路〕

図2は解が複数ある迷路の例で，一つ目の解が見つかった後に，他の解を見つけるために，迷路の探索を続ける。一つ目の解が見つかった後で，最初に実行される関数 visit の引数の値は カ である。この引数の座標を基点として二つ目の解が見つかるまでに，マスの“移動”は キ 回起き，その間に座標が (4, 2) のマスは ク 回“訪問”される。