応用情報技術者 2018年 春期 午後 問03

解答の論理構成

1. 【問題文】ではナイトの8方向を “図1の移動先①〜⑧” と定義し、
   　「①の場合、行方向は上に2マス、列方向は右に1マス移動するので、dv[1] は -2、dh[1] は1となる。」
   　と示しています。ここから
   　・上方向は負値、下方向は正値
   　・右方向は正値、左方向は負値
   　で表すという符号規則が確定します。
2. ④の位置を図1で確認すると、中央 (3行3列) から “下へ2、右へ1” です。
   　行方向　+2 ⇒ dv[4] = 2
   　列方向　+1 ⇒ dh[4] = 1 (すでに表1に掲載済み)
   　したがって ア は2となります。
3. ⑥の位置は “下へ1、左へ2” です。
   　行方向　+1 ⇒ dv[6] = 1 (既定値)
   　列方向　-2 ⇒ dh[6] = -2
   　よって イ は -2となります。
4. 以上より
   　ア：2
   　イ：-2
   　となり、【模範解答】と一致します。

誤りやすいポイント

• “上方向が負、左方向が負” という符号規則を逆に覚えるミス
• 図1の番号と実際の座標変位を取り違え、⑤と⑥などを入れ替えてしまうミス
• 行方向・列方向を0始まり配列と混同し、±1をずらして計算してしまうミス

FAQ

解答の導き方

1. 現在のマスへの記録（図3の行5）
   図3の行5で board[v][h] ← i により現在のマスに移動順序を記録します。問題文には「現在のマスに、移動順序を記録する。」とあるので、この直後の条件判定（図3の行6）は「記録した移動順序が全マスに達したか」を調べる場所です。問題文の（ii-1）には「記録した移動順序がM×Nに等しい場合、その経路を解の一つとして出力する。」とあるため、図3の行6の条件は $i=m\times n$ となります。ここで main（図5の行28〜29）の「m ← M」「n ← N」により $m,n$ が盤面の行数・列数を表すため、総マス数は $m\times n$ です。
2. 再帰呼び出しの引数（図3の行10〜11）
   図3の行10はfor( jを1から8まで ) で各移動先①〜⑧を順に調べます。問題文に「移動順序には、現在の移動順序に1を加えたものを指定する。引数の行と列には、移動先を指定する。」とあるので、再帰呼び出しの第一引数は $i+1$ です。移動先の行・列はdv[]、dh[] に対応するオフセットを現在の行・列に加えたものであると表記してある（「dv[]、dh[] はそれぞれ、八つの要素をもち、図1の移動先①〜⑧に対応する」）ため、第二引数は $v+dv[j]$、第三引数は $h+dh[j]$ となります。
3. バックトラック（図3の行14）
   再帰探索が戻ってきた後は「現在のマスの移動順序を取り消して、マスを通過していない状態に戻す。」（（ii-3））必要があります。図3の行5で board[v][h] に値を入れているので取り消しは board[v][h] ← 0 です。

• ウ：$i=m\times n$
• エ：$i+1$
• オ：$v+dv[j]$
• カ：$h+dh[j]$
• キ：board[v][h] ← 0

誤りやすいポイント

• 「=」の意味の取り違え：図3の行6は条件式なので等価比較の表現にして下さい。答案としては $i=m\times n$、あるいは「iがm×n」など等価を示す記述で正答となります。擬似コードの記法（言語により '=' が代入になる場合がある点）と混同しないよう注意してください。
• iを増やし忘れる：再帰呼び出しで移動順序を増やさずにsearch(i, ...) のようにしてしまうと探索が正しく進みません。必ず $i+1$ を渡します。
• バックトラック忘れ：board[v][h] を0に戻さないと、そのマスが既に通過済みと見なされて他の経路が探索できなくなります。必須の操作です。
• 添字の基点を誤る：dv[]、dh[] は問題文で添字を1から始めると明示されています。forループがjを1から8まで回すことと整合させて下さい。
• dv/dhの役割混同：dv[] は行方向、dh[] は列方向のオフセットです。行と列を取り違えないようにします。

FAQ

解答の論理構成

1. 盤面の拡大理由
   • 問題文では「ナイトの移動先が盤面の範囲外となった場合の判定処理を簡略化するために、図6のように盤面を…拡大して表現する」とあります。
   • 図6の“変更後の盤面”を見ると、実際に移動可能な範囲の外側に幅 2 マス分の“番兵（値1）”を配置しています。
2. 元のprintBoardの挙動
   • 行番号 20 と 21 はそれぞれ
     for( v を 1 から m まで 1 ずつ増やす ) for( h を 1 から n まで 1 ずつ増やす )
   • これは拡大前（番兵なし）を前提に「実盤面だけ」を表示するループです。
3. 拡大後に必要なオフセット
   • 図6より、実盤面の左端は列 3、上端は行 3 にシフトしています。
   • 右端・下端も同様に 2 マス分だけ後ろへ伸びているので、最終行列はm+2, n+2になります。
4. 従って修正箇所
   • 行番号 20 を
     for( v を 3 から m+2 まで 1 ずつ増やす )
   • 行番号 21 を
     for( h を 3 から n+2 まで 1 ずつ増やす )
   と書き換えることで、番兵を除いた“真の盤面”のみを印字できます。

誤りやすいポイント

• 「幅1マス」ではなく 2マス の番兵が付くことを見落としやすい。
• searchの境界判定を削除した結果、printBoardも変更が必要と気づかずそのままにしてしまう。
• mとnを更新して盤面全体を8×7にする、と誤解してループ上限をm、nで置き換えない。

FAQ

解答の論理構成

1. 変更前のメインプログラムは
   　「32:　search( 1, 1, 1 )」
   　と記載され、searchの第2・第3引数に「行1、列1」を渡していました（【問題文】図5）。これは“行1列1のマスを起点とする”という処理仕様（【問題文】「(1) 移動順序1、行1、列1で、再帰関数searchを呼び出す。」）に対応しています。
2. 〔盤面の表現の変更〕では
   　「盤面をナイトが移動できるマスが全て含まれる範囲まで拡大して表現する。」
   　と明記されており、盤面の周囲に番人（境界用の1）が2マス分置かれる構造に変わります。この“2マス分”の根拠は、ナイトの最大移動幅が縦横方向いずれも2であるためです（【問題文】表1のdv[], dh[] 参照）。
3. 拡大後の配列board[][] では、
   　元々の「行1列1」は “外側に2マス分” シフトし、
   　内部表現上の座標は「行3列3」になります。
4. したがって、起点を正しく指定するには
   　行番号・列番号ともに +2した値をsearchに渡す必要があります。
5. よって、変更箇所（行番号）と変更後の呼び出しは
   　【模範解答】
   　行番号：32
   　変更後のプログラム：search(1,3,3)
   　となります。第1引数「1」は移動順序を示すため変更しません。

誤りやすいポイント

• 「+2のシフト」に気付きながら、第1引数まで3に変更してしまう。移動順序は常に1から開始するため不正解になります。
• 盤面を広げたあとも境界判定コードを削除し忘れ、テスト時に動作がおかしくなる。
• シフト量を1だけと誤認し「search(1,2,2)」と書いてしまう。ナイトは2マス跳ぶことを思い出しましょう。

FAQ

解答の論理構成

1. 変更前の境界判定
   • 再帰関数searchの行番号 2 と 3 は
     【問題文】図3
     if( v が 1 以上, かつ, m 以下 )
     if( h が 1 以上, かつ, n 以下 )
     という二重の境界チェックを行っています。
2. 盤面を外枠付きに拡大
   • 【問題文】図6の変更後の盤面では、有効域外をすべて 1 に初期化し、
     ナイトが実際に移動可能なマスだけを 0 にしています。
   • この方式を取ると、配列外アクセスは発生せず、境界判定は
     行 4 のif( board[v][h] が0 ) のみで十分になります。
3. 削除が必要な行
   • 行 2, 3 を消すと対応する endif が不要になるため、
     行 16, 17 も同時に削除する必要があります。
   • これにより階層が崩れず、処理内容も所定どおり簡略化されます。
4. 結論
   • 削除対象は “2, 3, 16, 17” です。

誤りやすいポイント

• 外枠を追加したあと 4 行目のboard[v][h] が0まで削除してしまい、
  「未訪問判定」ができなくなる。
• 行 2 か 3 のどちらか一方だけを残し、ロジックエラーではなく
  コンパイルエラーが発生して戸惑う。
• 行番号の振り直しを忘れ、答案欄に誤った番号を記入する。
• 盤面外を 1 で埋める理由を「通過済みマスの判定」と混同し、
  sentinelの役割を取り違える。

FAQ