最短経路の求め方です。
この記事から読む場合はまずは問題編を見てください
基本的にはスタート地点から隣接するマスに移動時間を設定していきます。
図示するとこんな感じですね。
ですが、今回の問題の場合、昇り降りするより回りこんだほうが早いという現象が起こります。
オレンジ色を一段高い場所として同様に計算してみましょう。
背景が青くなっている場所は赤い場所を13の時間として計算した場所です。
ここは回りこんだことにより12と計算されますので、再度計算が必要になります。
このように、一直線で進むより回りこんだほうが早い地形が出てくる場合は、
次に探査するマスの順序を移動時間の小さい順にしたほうがよいです。
先ほどのマップですと、3→6→9の順で探索していくことで、12が先に埋まり、
13と計算して進めていた部分がなくなるので無駄が減ります。
とはいえ、250x250のマップに対してこの探索順序の入れ替えをしなくても
1ms以下で探索が終わったのでさほど速度的には貢献しないかもしれません。
ゴールが決まっている場合は、ゴールから遠ざかる方向に対して探索しても無駄に終わることが多いので、
この優先度にゴールまでの予想時間を加えることで、効率よい探索ができるようになります。
これが「A*」と呼ばれるアルゴリズムです。
今回は1マスを進むのが大体3かかるので、ゴールまでの単純距離×3を予想時間としてカッコ内に併記しています。
黄色い部分はスタートから近いので普通ならここからの探索もするのですが、
緑の部分の優先度が15のため、黄色い部分からの探索がされることはありません。