基本情報技術者 2019年 春期 午後 問11
次のJavaプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
〔プログラムの説明〕
升目を用いて表現された迷路と、迷路上に置かれて外部から操作される駒を表すプログラムである。
迷路は、駒が通れる升（以下、通路という）と通れない升（以下、壁という）から成る。迷路の外周は壁である。通路のうちの一つが開始地点であり、開始地点でない通路のうちの一つがゴール地点である。本問で扱う迷路を、図1に示す。
迷路上の升の位置は、2次元の座標(x, y)で表す。xとyはともに非負整数である。ある位置を基準として、xの値が大きくなる方角を東、小さくなる方角を西、yの値が大きくなる方角を南、小さくなる方角を北とする。
駒は、東西南北のいずれかを向いており、向いている方角を基準として、次の三つの操作を外部から受け付ける。
① 左の方向に向きを変える。
② 右の方向に向きを変える。
③ 隣接する前方の升が通路なら、1升前進する。
(1) クラスMazeは迷路を表す。コンストラクタの引数には、文字列で表現した迷路と、迷路の西端から東端までの升の個数を指定する。迷路を表現する文字列は、1升を表す文字を西から東に向かって順に並べた1行分の文字列を、北から南に向かって順に連結したものである。升の種類は、char型の値で表す。“*”は壁を、それ以外の値は通路を表し、“S”は開始地点を、“G”はゴール地点を表す。引数に誤りはないものとする。
メソッドgetStartLocationは開始地点の座標を返す。メソッドisGoalは指定された座標の升がゴール地点であればtrueを、それ以外はfalseを返す。メソッドisBlankは指定された座標の升が通路ならばtrueを、壁ならばfalseを返す。
(2) クラスPieceは、迷路上に置かれる駒を表す。コンストラクタの引数で迷路を指定する。インスタンスは、最初は、開始地点に位置し、北を向いている。
メソッドturnLeftは左の方向に、turnRightは右の方向に向きを変える。
メソッドtryStepForwardは、隣接する前方の升が通路なら1升前進し、前進した方角を履歴リストに追加してからtrueを返す。通路でなければ、前進せずにfalseを返す。
メソッドisAtGoalは、ゴール地点にいればtrueを、それ以外はfalseを返す。
メソッドgetHistoryは、履歴リストを返す。
(3) 列挙Directionは、方角を表す。
メソッドleftは列挙定数が表す方角に向かって左の方角を、rightは右の方角を返す。
(4) クラスLocationは、迷路上の升の位置を示す座標を表す。
(5) クラスPlayMazeは、図1に示す開始地点からゴール地点に至るまで駒を操作し、その後、履歴リストを表示する。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
a, bに関する解答群
ア：%
イ：&
ウ：*
エ：+
オ：-
カ：/
キ：^
ク：|
cに関する解答群
ア：direction
イ：direction.dx, direction.dy
ウ：location + direction
エ：location.x + direction.dx, location.y + direction.dy
dに関する解答群
ア：(ordinal() + 3) % 4
イ：(ordinal() + 3) / 4
ウ：(ordinal() - 1) % 4
エ：(ordinal() - 1) / 4
模範解答
a：ウ、b：ア、c：エ、d：ア
解説
解答の導き方
この問題では、迷路の文字列の中から座標を計算する方法、駒の次の座標を求める方法、方角を左に変える方法を考えます。
まず、迷路の升は、北の行から南の行へ、各行の中では西から東へ並んで文字列に格納されています。したがって、座標 の升が文字列の何文字目にあるかは、上から 行分の文字数に、行内での位置 を加えて求められます。1行の幅がwidthなので、位置は です。
このため、プログラム1のisGoalとisBlankで、yにwidthを掛けてxを足す演算を選びます。つまり、aには乗算を表す「」が入ります。計算した位置の文字を取り出し、「G」ならゴール、「」以外なら通路と判定しています。
次に、locationOfでは、文字列の中で見つけた位置indexから、座標を逆算します。1行の幅で割った余りが、行の中での位置、つまりx座標です。よって、bには剰余を求める「%」が入ります。一方、indexをwidthで割った整数の商が、上から何行目かを示すy座標です。
例えば、幅が7で、開始地点の座標が なら、文字列中の位置は です。15を7で割ると、商は2、余りは1です。これにより、y座標が2、x座標が1と分かります。
プログラム2のtryStepForwardでは、現在位置に、向いている方角の移動量を加えて次の座標を作ります。例えば、北を向いているときの移動量は なので、x座標はそのまま、y座標だけが1小さくなります。Locationのコンストラクタはx座標とy座標の二つを受け取るため、cには「location.x + direction.dx, location.y + direction.dy」が入ります。
次の升が通路ならlocationを更新し、進んだ方角を履歴に加えます。壁なら位置を変えず、履歴にも加えません。つまり、履歴に残るのは、向きを変えた記録ではなく、実際に前進した方角です。
最後に、プログラム3の方角の並びを確認します。列挙定数はNORTH、EAST、SOUTH、WESTの順です。これは、右に向きを変えるたびに次の定数へ進む並びです。したがって、左に向きを変えるには、定義順を一つ戻ります。
ただし、NORTHの位置は0です。そこから単純に1を引くと負の値になり、配列の位置として使えません。そこで3を足して4で割った余りを使えば、NORTHから左に向いたときは位置3、つまりWESTになります。よって、dには「(ordinal() + 3) % 4」が入ります。
誤りやすいポイント
- 文字列の位置を求める式で、x座標とy座標を逆にしないようにします。行が変わるごとにwidth文字進むため、式は です。
- 座標を文字列の位置に直す計算と、文字列の位置から座標に戻す計算を混同しないようにします。位置からx座標を求めるのは余り、y座標を求めるのは整数の商です。
- cでは移動量を現在位置に加えます。direction.dxとdirection.dyだけでは移動量しかなく、Locationを作るための新しいx座標とy座標になりません。
- 左右の向きは、列挙定数の並びだけで判断せず、各方角の並びと照らし合わせます。この問題では、定義順が右回りなので、左回りは一つ前の位置です。
- 履歴に加わるのは、前進できたときだけです。壁にぶつかって前進できなかった試行や、方向転換は履歴に含まれません。
FAQ
Q: なぜ座標から文字列の位置を求めるとき、yにwidthを掛けるのですか？
A: 1行下へ進むと、文字列の中ではその行の升の数だけ先へ進むからです。widthが1行分の升の数なので、y行分では 文字進み、さらに行内でx文字進みます。
A: 1行下へ進むと、文字列の中ではその行の升の数だけ先へ進むからです。widthが1行分の升の数なので、y行分では 文字進み、さらに行内でx文字進みます。
Q: なぜ左向きの計算に3を足すのですか？
A: 定義順で一つ前の位置を使いたいからです。位置0のNORTHから一つ戻ると負の値になりますが、3を足して4で割った余りなら位置3となり、WESTを選べます。
A: 定義順で一つ前の位置を使いたいからです。位置0のNORTHから一つ戻ると負の値になりますが、3を足して4で割った余りなら位置3となり、WESTを選べます。
Q: 壁に向かって前進しようとした方角も履歴に残りますか？
A: 残りません。tryStepForwardは、前方が通路の場合にだけ位置を更新し、履歴に方角を加えます。
A: 残りません。tryStepForwardは、前方が通路の場合にだけ位置を更新し、履歴に方角を加えます。
関連キーワード: 2次元座標、剰余演算、整数除算、列挙型、リスト
設問2：
問題文を見る プログラム5のαの位置に次の処理を挿入し、実行結果として、図2に示す方角のリストを得た。駒は、開始地点からリストの方角の順に1升ずつ進むと、直前の升に戻る（正反対の方角に向きを変えて進む）ことなく、ゴール地点に至ることができる。に入れる正しい答えを、解答群の中から選べ。
for (int i = e; i < history.size(); i++) {
if (history.get(i - 1) == history.get(i).left().left()) {
history.remove(f);
history.remove(f);
i = i < 2 ? 0 : i - 2;
}
}
eに関する解答群
ア：-1
イ：0
ウ：1
fに関する解答群
ア：i
イ：i + 1
ウ：i - 1
模範解答
e：ウ、f：ウ
解説
解答の導き方
まず、駒がゴールまで進んだときの履歴を考えます。迷路の通路をたどると、履歴には次の方角が順に記録されます。
[SOUTH, EAST, EAST, EAST, NORTH, NORTH, EAST, WEST, SOUTH, SOUTH, EAST, SOUTH, SOUTH, WEST, WEST, WEST, WEST]
この履歴には、進んだあとに同じ道を戻る動きも含まれています。設問では、直前の升に戻る動きを取り除きます。
-
2つの方角が正反対なら、取り除けます。
例えば、EASTに進んだ直後にWESTに進むと、元の升に戻ります。Directionのleftを2回使うと正反対の方角になるため、条件式はこのような組合せを見つけています。 -
eは1です。
履歴の位置は0から始まります。隣り合う2つの方角を調べるには、1つ前の位置と現在の位置を比べます。そのため、最初の位置iは1にします。0から始めると、1つ前を表す位置がマイナス1になり、履歴の範囲外を参照してしまいます。 -
fはi - 1です。
取り除くのは、位置i - 1と位置iの2つです。1つ目を位置i - 1から削除すると、後ろにあった位置iの要素が位置i - 1に移ります。そこで、同じ位置i - 1をもう一度削除すれば、2つの方角を両方取り除けます。 -
削除後は、少し前の位置から調べ直します。
要素を削除すると、前後にあった方角が新たに隣り合うことがあります。そこで、iを戻してからループを続け、削除によってできた新しい組合せも調べます。
実際に履歴を処理すると、次のようになります。
最初にEASTとWESTを削除すると、その近くの方角が新たに隣り合います。そのため、iを戻して調べ直す必要があります。最終的に残る履歴は、設問に示された方角のリストになります。
誤りやすいポイント
-
eを0にしないこと
比較では1つ前の位置も使うため、最初のiは1です。iを0にすると、履歴の範囲外を参照します。 -
2回目の削除位置をiにしないこと
1つ目を削除すると後ろの要素が前に詰まります。同じ位置i - 1をもう一度削除することで、隣り合う2つの方角を取り除けます。 -
削除後に調べ直す位置を見落とさないこと
要素を削除すると、それまで離れていた方角が隣り合い、正反対の組合せになることがあります。iを戻す処理は、その組合せを見逃さないためにあります。
FAQ
Q: なぜ正反対の方角を2つとも削除できるのですか？
A: その2つの方角に続けて進むと、出発した升に戻るからです。進んだ分と戻った分が打ち消し合います。
A: その2つの方角に続けて進むと、出発した升に戻るからです。進んだ分と戻った分が打ち消し合います。
Q: なぜ同じ位置を2回削除するのですか？
A: 1つ目を削除すると、後ろの要素がその位置に移るためです。同じ位置を再度削除すると、もう一方も削除できます。
A: 1つ目を削除すると、後ろの要素がその位置に移るためです。同じ位置を再度削除すると、もう一方も削除できます。
Q: 履歴から要素を削除すると、駒が記録した履歴も変わりますか？
A: 変わりません。getHistoryは履歴のコピーを返すため、ここで削除しているのは、受け取ったリストの内容です。
A: 変わりません。getHistoryは履歴のコピーを返すため、ここで削除しているのは、受け取ったリストの内容です。
関連キーワード: リスト、インデックス、列挙型、ループ、状態遷移
