以前、CodeIQでモンハンとのコラボ問題で「電脳体「キュラゲタム」を討伐せよ！」というのがあって、
解答募集期間も過ぎたので解説記事でも書こうと思ったんですが…。
期限が終わると問題すら見られないようになってしまうんですね、残念。
問題の概略を書きます。
標準入力からこんなデータをもらいます。
4 5
32445
33434
21153
12343
最初がマップの大きさ、今回は4×5のマップという意味で、それ以降が実際のマップデータです。
数値は高さを表していて、小さいほど低く大きいほど高いという意味になります。
このマップを左上からスタートして、すべての山頂を通り左上に戻る最短時間を求めるのが問題です。
山頂とはマップの中で一番高い点、今回だと5の高さの部分2箇所です。
移動は隣接しているマスに移動でき、斜めには移動できません。
移動時間は同じ高さなら3、1段下がる場合は2、1段上がる場合は11かかります。
2段以上の段差は上りでも下りでも移動できません。
この問題は左上と山頂、または山頂と山頂の最短経路を求める問題と
どういう順序でそれぞれの山頂を巡っていくかという巡回セールスマン問題とに別れます。
私も、最短経路の方が難しそうと思って挑んだのですが、
実際に難しいのは巡回セールスマン問題の方でした。
最初に提出した解答はマップが大きくなると一気に時間がかかるようになりタイムアウト。
「最短経路の求め方」と「巡回セールスマン問題」の2つに分けて記事にします。