【解説】情報関係基礎 平成30年度 センター試験

第3問（選択）

問1

空欄 アイ・ウエ・オカ・キ・クケ

（ア, イ）:（6, 2）

（ウ, エ）:（2, 4）

（オ, カ）:（7, 8）

キ : 3

（ク, ケ）:（3, 8）

ここでは、袋小路を黒く塗る手段を考えます。

まず前提条件を確認しておきましょう。

• 道は縦横方向のみ進むことができる
• 環状の道や2×2以上の道、孤立した道は考慮しない
• 道のマスで、上下左右のうち三方が壁であるものを行き止まりと呼ぶことにする
• 行き止まりのマスは、袋小路の先端であり黒く塗ることができる

また、行き止まりを塗る方法として、手順1が示されているので、フローチャートで考えてみましょう。フローチャートを以下に示します。

ちょっと雑ですがお許しを。rowが行、columnが列を表します。

フローチャートに沿ってマスを塗っていった図は以下のようになります。

例えば1-1という数字では1回目の1番目に塗られたマス、1-2では1回目の2番目に塗られたマスであることを示します。

こういった問題の場合問題を解きながら実際に自分でも確認しながら進めていくといいでしょう。

処理を一通り終えると、スタート地点からゴール地点まで迷わずにいける道を見つけ出すことができます。

問2

コ : ⓪ 0

サ : ⑥ tate−1

シ : ⑦ yoko−1

ス : ② Masu[x, y]=0

セ : ③ 3

ソ : ① 1

問1ではrowやcolumnといった変数を使っていましたが、問2ではtateやyokoといった変数が登場しますね。次からは全て解いてから解説を作ります…。

さて、問2で登場する変数は

tate（行数）、yoko（列数）、Masu[x, y]（配列の要素）、nutta（行き止まりを塗ったか）があります。

Masu[x, y]には、マス（x, y）が壁ならば1が、道であれば0が、またスタートやゴールならば9があらかじめ格納されている。マスを塗ることは、対応する配列の要素の値を1にすることである。

とあるので、Masu[x, y]が行き止まりであるとわかったら、Masu[x, y]を1にしてnuttaを1にするのだろうなと想像できます。

実際に31ページ図5のプログラムを見てみると（07）行でMasu[x, y]←ソ, nutta←1とあります。

プログラムを見てみましょう。それぞれ簡単に説明をしておきます。

空欄コ

（02）nutta←コ　については、前提条件にあった

変数nuttaは、ステップ1で行き止まりを1マスでも塗ったかどうかを示す。

と、（07）Masu[x, y]←ソ, nutta←1　をみるとわかります。

（07）行目のプログラムは、（06）行目のIF文を満たす時に実行されます。IF文を実行してnuttaに1を代入するので、実行前にはnuttaは0である必要があります。

よってコは0であると考えることができます。

空欄サ・シ

空欄サとシについては、XとYの範囲がわかっていれば解答できます。

今回は行き止まりであるかどうかを判定するプログラムです。すなわち問1と同じように外周については除いて実行をします。

ですので、今回のプログラムの実行範囲は以下の赤線で囲まれた範囲です。

前提条件に、

変数tateと変数yokoには、迷路の行数と列数があらかじめ格納されている。

とあるので、tate=9、yoko=11であると考えることができます。

よって赤線で囲まれた範囲はY : 2から（tate−1）、X : 2から（yoko−1）となります。

空欄ス・セ・ソ

プログラムの（06）行目から（08）行目は、行き止まりを見つけた際に道を塗るという動作を表します。

前提条件に

マス（x, y）が壁ならば1が、道であれば0が、またスタートやゴールならば9があらかじめ格納されている。マスを塗ることは、対応する配列の要素の値を1にすることである。

とあるので、行き止まりを見つけたらそのマスの対応する配列を1にするという動作です。

問1の前提条件に

道のマスで、上下左右のうち三方が壁であるものを行き止まりと呼ぶことにする。

とあります。ですので、調べたいマスの三方が壁（すなわち1）である場合、行き止まりであるのでそのマスを1にします。

例えば、プログラムを実行する一番最初のマスである（x, y）=（2, 2）は周り三方が壁（1）なので、行き止まりとわかります。

このように、Masu[x, y]が0でMasu[x, y]の三方が1であれば行き止まりということでMasu[x, y]を1にします。

よってプログラム（06）行目から（08）行目は

（06）もし Masu[x, y]=0 かつ s=3 ならば

（07）　　Masu[x, y]←1, nutta←1

（08）を実行する

となります。

問3

タ : ②x

チ : ③y

ツ : ⓪Masu[i, j]=0

テ : ①Masu[i+1, j]

ト : ②Masu[i, j+1]

ナ : ⑥i+di

ニ : ⑧j+dj

問3で登場する手順2では、

行き止まりを見つけたら、その分岐点に到着するまで新たにできた行き止まりを連続して塗る。

とあります。この文だけではいまいちわかりませんが、手順2のステップ3に

着目したマスの上下左右に隣接するマスのうち、新たに行き止まりになった可能性のあるマスに着目する。ステップ2に進む。

とあるので、手順2では、行き止まりのマスを塗ったあと、上下左右にまた行き止まりとなりそうなマスがあった場合そのマスに移動して検証するということがわかります。

こういった問題の場合、私は問題文を読んで、ある程度こういった動きをするだろうなと予測してからプログラムと照らし合わせて、プログラムを埋めていきます。

今回もそのように解説していきます。

まず、プログラムを見て、問2までと同じく（x, y）=（2, 2）から始めることがわかります。

（2, 2）から行き止まりを塗っていきますが、塗っていく中で今後行き止まりになりそうなものを赤で囲ってみます。下図のようになりますね。

（2, 2）→（2, 3）→（2, 4）と遷移するだろうと予測します。

実際にどのように遷移していくか、いくつか試してみて正解を見つけましょう。

少し心配だったら、それ以降についてもいくつか確認しておくといいでしょう。

時間がある方は、色分け通りに色を塗っていけることを確認しておくといいでしょう。