Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成30年度春季応用情報午後問3

平成30年度春季 応用情報技術者試験(AP)の午後問題3は、再帰による深さ優先探索を用いたナイトの巡回問題でした。

IPA 独立行政法人 情報処理推進機構:問題冊子・配点割合・解答例・採点講評(2018、平成30年)」のページでまだ解答が示されていませんので、自分なりの解答を載せておきます。

設問1
ア:2 イ:-2
設問2
ウ:iがM・N エ:i+1 オ:v+d[j] カ:h+dh[j] キ:board[v][h] ← 0
設問3

(1)

20行目:vを3からm+2まで1ずつ増やす
21行目:hを3からn+2まで1ずつ増やす

(2)

32行目:search(1, 3, 3)

(3)

2,3,16,17行目

設問1,2(h30h_ap_pm3_1.c)

設問1,2の実行結果

$ gcc h30h_ap_pm3_1.c && ./a.out
  1  8  3
  4 11  6
  7  2  9
 10  5 12

  1 12  3
  4  9  6
  7  2 11
 10  5  8

設問3(h30h_ap_pm3_2.c)