Y箱

数字の入った盤面を移動するコストの問題その2

今回は右と上下のどちらにでも移動できます。







5行の盤面のあるとなりあう2列A、Bを考えます。

A1 B1
A2 B2
A3 B3
A4 B4
A5 B6

このとき、A列のそれぞれのマスまでの最小のコストが判明しているとすれば、B列の最小のコストが計算できます。

たとえば、任意のA列からB2へのルートは、法則に従えば、
 - A1 B1 B2
 - A2 B2
 - A3 B3 B2
 - A4 B4 B3 B2
 - A5 B5 B4 B3 B2
の5通りになります。
A列ではそこまでの最小コスト、B列ではそのマスのコストを採ると、それぞれのルートを通ったときのコストが計算でき、B2までの最小コストが計算できます。
そして、一番左の列の最小コストはその列そのもののコストなので、2列目から順に全ての最小コストを計算していけば、答が出ます。





・ allnums-between
 aとbの間の数を返す関数。 2 と 5 なら 2 3 4 5が返ります。

・ sum-of-col
 指定の列のn行目からm行目のコストを加算する。

・ cost-of
 となりあった2列の指定の場所から指定の場所までの総コストを計算します。
 上の説明のルートの計算です。

・ minimum-cost
 指定のマスのコストを計算します。
 1つ前の列の最小コストが計算されていることが前提です。
 1つ前の列の全てのマスからそのマスまでの全てのコストを計算して、最小値をそのマスのコストとします。

・ calc-all-min-coste
 いちばん左の列から順に、最小コストを計算します。
 0列めは計算対象外なのですが、ガードに0が出るようにすることで、計算に含めてしまっています。時間的にはロスですね。

・ pe-82-with-file
 ファイルからデータを読んで、計算する関数に渡して、最後に最小の値を取ります。