応用情報技術者 試験情報＆徹底解説

問題文中で述べられている迷路の表現方法(迷路図情報)をまとめると、以下のようになります。

• 各マスの位置をx座標とy座標で表し、各マスに対応するマス情報を設定して迷路を表現する
• 進入不可の障害物と外壁マスはNGフラグ、始点マスと訪問済のマスには足跡フラグ、まだ進んでいないマスにはOKフラグが設定される

また、探索の方法は以下のとおりです。

• 始点のマスから、"進む"または"戻る"の2種類の"移動"によって探索を行う
• "進む"は、上(①y座標を1増やす)⇒右(②x座標を1増やす)⇒下(③y座標を1減らす)⇒左(④x座標を1減らす)の順で行う
• "進む"ことができない場合、そのマスをOKフラグに戻してから1つ前のマスに"戻る"
• 終点に到達するまで、"進む"または"戻る"を繰り返す

(1)と(2)のどちらも図1で1つの終点に到達するまでのプロセスなので、まとめて解説します。

"移動"とは、"進む"と"戻る"の二つの動作です。"進む"動作は、上⇒右⇒下⇒左の順で行われることを踏まえて、初期状態から"移動"が13回発生するまでの流れを追跡すると以下のようになります。オレンジ色のマスは足跡フラグが設定されているマス、すなわちスタックに格納されている座標を表しています。

1. 上に進めるので、始点(1,1)から上のマス(1,2)に進む
2. 上に進めるので、(1,2)から上のマス(1,3)に進む
3. 上に進めるので、(1,3)から上のマス(1,4)に進む
4. 上に進めるので、(1,4)から上のマス(1,5)に進む
5. 上に進めないので、(1,2)から右のマス(2,5)に進む
6. 4方向のいずれもOKマスではないので、(2,5)から左のマス(1,5)に戻る
7. 4方向のいずれもOKマスではないので、(1,5)から左のマス(1,4)に戻る

ここまでが7回の移動で、スタックには4つの座標が格納されています。

8. 4方向のいずれもOKマスではないので、(1,4)から左のマス(1,3)に戻る
9. 右に進めるので、(1,3)から上のマス(2,3)に進む
10. 4方向のいずれもOKマスではないので、(2,3)から左のマス(1,3)に戻る
11. 4方向のいずれもOKマスではないので、(1,3)から左のマス(1,2)に戻る
12. 4方向のいずれもOKマスではないので、(1,2)から左のマス(1,1)に戻る
13. 右に進めるので、(1,1)から上のマス(2,1)に進む

ここまでが13回の移動で、スタックには(1,1)と(2,1)の2つの座標が格納されています。さらに探索を続けると、(3,1)→(3,2)→(5,2)→(5,5)とたどって終点に到達することとなります。この探索において"訪問"されなかったマスは、×印を付けた(5,1)(3,4)(4,4)の3マスです。

∴(1)＝3
　(2)＝2

解説の便宜上、プログラムに行番号を振っておきます。〔イについて〕
4行目のif文の条件式より、5～8行目は訪問したマスが終点だったときの処理であることがわかります。問題文を読むと「終点にたどり着いた時点でスタックの内容を順番にたどると，それが解の一つになる」とあり、現在のスタックの内容で解の一つが確定することがわかります。メインプログラムのほうでは解を出力する処理として配列 paths の印字処理がありますが、関数 visit のほうには配列 paths に値を設定する処理がどこにも記述されていません。このままだとメインプログラムで出力される paths は常に空となってしまいますから、5～8行目で行うべきは配列 paths に解を格納する処理であると判断できます。

配列 paths[u][v] は2次元配列で、uは解の番号を示す添字、u番目の解を構成する各座標の順番を表すのがvです。
最初に見つかった解は paths[0] に格納、2番目に見つかった解は paths[1] に格納という感じになります。プログラム中では解を見つけた総数を保持する変数として sol_num があります。変数 sol_num の初期値は0であり、8行目で解が見つかるごとに1ずつ増えていくようになっています。変数 sol_num を添字uに使えば、1つ目の解が見つかったときには paths[0]、2つ目の解が見つかったときには paths[1] が代入先となるので解を適切に格納することができます。

次に添字vに使う式を考えます。5行目にあるfor文は配列 stack_visit の全要素に対して順番に処理を繰り返しています。[イ]に代入されることとなる stack_visit[k] は、スタック内のk番目の座標情報を示していますから、
というように、paths[sol_num]の0からk番目の位置に順に代入すれば、stack_visit に格納されている解の情報を paths[sol_num] にコピーすることができます。したがって、添字vにはループ変数であるkを使うのが適切です。

∴イ＝paths[sol_num][k]

〔ウについて〕
空欄ウを含む23行目の処理は、訪問先が終点ではない場合の最後に実行される処理です。

else節内の処理を初めから順に追っていくと、10行目で変数 stack_top が1加算されています。これはもし上下左右いずれかのマスに移動した場合、移動先のマスに対する関数 visit の最初でスタックに座標を積む処理があるため、移動前にあらかじめスタックの最後尾を1つ後ろにずらしておく意味合いがあります。
そして11～22行目では、上⇒右⇒下⇒左の順に4方向へ"進む"試みを行っています。もし移動可能であれば移動先のマスに対して関数 visit が呼び出されますし、移動不可であれば何もせずに次の処理に移る形です。
最後に、23行目で変数 stack_top への代入処理が行われています。

23行目が実行されるのは、4方向すべてのマスがOKフラグではなく（訪問済・壁・障害物マスのいずれかで）先に"進む"ことができないときです。10行目でスタックの最後尾を1つ後ろにずらしたのは、"進む"ことを前提としたものなので、先に進めないときにはスタックの最後尾を元に戻しておかなければなりません。他に変数 stack_top に代入する処理はないので、23行目でそれを元に戻す、すなわち変数 stack_top を1減算する必要があります。この処理がないと、現在処理中のマスがスタック上の経路から取り除かれないため正しい解となりません。

∴ウ＝stack_top - 1

〔エについて〕
空欄エのある25行目はif文の外にあるので、終点に到達したかどうかにかかわらず実行される処理です。

仮に終点に到達していない場合、25行目は4方向へ"進む"試みを行ったあとに実行されます。〔迷路の解を見つける探索〕の「4方向いずれにも"進む"ことができないときには，現在いるマスのマス情報をOKフラグに戻し，一つ前のマスに"戻る"」という説明より、25行目の処理は「現在いるマスのマス情報をOKフラグにする」であると推測できます。終点に到達した場合も、新たな解を見つけるために終点から一つ前のマスに戻ることになるため、25行目の処理は上記の内容で問題ありません。

本問ではマス情報全体が迷路図情報と呼ばれていることから、マス情報の変更処理は表1で示されている配列 maze[x][y] に対して行えばよいとわかります。2行目で"訪問"した際に maze[x][y] に VISITED を設定していること、3行目でスタックに入れている座標が(x,y)であることから、現在いるマスは(x,y)で表せることがわかります。したがって、OKフラグの設定先は maze[x][y] となります。

∴エ＝maze[x][y]

〔オについて〕
図4を確認すると、7行目のif文の条件式が真の場合、"迷路は見つからなかった"と印字する処理が実行され、逆に偽の場合、解を格納した配列 paths を印字する処理が実行されます。これより、7行目の条件式には「解が見つかっていない」ときに真となる式が当てはまると判断できます。すべてのマスの探索が終了したとき、見つかった解の個数は変数 sol_num に格納されており、解が見つからなければ変数 sol_num は初期値である0のままです。したがって、条件式としては「sol_num が0と等しい」という形になります。

表1において、整数型の変数は stack_top または sol_num しかありませんが、stack_top は探索が終了したとき常に0になっているので、解が見つかったかどうかの判定に使うことはできません。

∴オ＝sol_num