ScalaでProject Euler（119）

ダイクストラ法への道第1弾です。
問題に載っている例で考えてみましょう。

131 673 234 103  18
201  96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524  37 331

左上をスタートして動けるのは右と下だけです。左上から各マスへの最小経路和を求めることを考えます。まず、太字にした左上ですが、



131 673 234 103  18

201  96 342 965 150

630 803 746 422 111

537 699 497 121 956

805 732 524  37 331

ここはそのまま131です。次にその右下の96を見てみましょう。



131 673 234 103  18

201  96 342 965 150

630 803 746 422 111

537 699 497 121 956

805 732 524  37 331

ここへの経路はその上の673か左の201を通ってここへ辿りつきます。ですから、673までの経路の最小和と201までの最小経路和の最小＋96が最小経路和になります。すなわち再帰的で求められるわけですが、メモ化すれば素早く計算できます。順番を適切にすればDPにもなります。左から各列を上から下に計算すれば、各マスの最小経路和を計算するときにその手前のマスは全て計算済みになっています。例えば、



131 673 234 103  18

201  96 342 965 150

630 803 746 422 111

537 699 497 121 956

805 732 524  37 331

赤字はすでに最小経路和が求まっているマスです。太字の96は673と201の最小経路和がすでに求まっているので、96までの最小経路和が即求まります。

val source = io.Source.fromFile("matrix.txt")
val a = source.getLines.map(s => s.split(',').map(_.toInt)).toArray
val N = a.size

for(x <- Iterator.range(0, N); y <- Iterator.range(0, N))
    if(x == 0) {
        if(y != 0)
            a(y)(x) += a(y-1)(x)
    }
    else if(y == 0) {
        if(x != 0)
            a(y)(x) += a(y)(x-1)
    }
    else {
        a(y)(x) += a(y)(x-1).min(a(y-1)(x))
    }

println (a(N-1)(N-1))