Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-04-21

Project Euler #81

| 01:01 | Project Euler #81 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #81 - nitoyon.dispatchEvent(null)

下記の5次の正方行列で、左上のセルから開始し右下のセルで終わる道を探索する。ただし下方向と右方向にのみ移動できるものとする。一番小さなパスは下で太字で示されたものである。このときの合計は2427になる。

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

今、31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 左上のセルから開始し右下のセルで終わりかつ右方向と下方向にのみ移動するときの最小の道の和を求めよ.

Problem 81 - PukiWiki

80×80だけど、DP の標準的な適用例なのでそのまま解く。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem81 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem81(){
        var list:Array = data.split(/\r?\n/);
        var a:Array = [0];

        for each (var line:String in list) {
            var s:Array = line.split(/,/);
            for (var i:int = 0; i < s.length; i++) {
                a[i] = (a[i] == undefined ? Infinity : a[i]);
                a[i] = Math.min(a[i], i == 0 ? Infinity : a[i - 1]) + parseInt(s[i]);
            }
        }

        t.text = a[a.length - 1];
    }

    private var data:String = <>4445,2697,5115,718,2209,2212,654,4348,3079,6821,7668,3276,8874,4190,3785,2752,9473,7817,9137,496,7338,3434,7152,4355,4552,7917,7827,2460,2350,691,3514,5880,3145,7633,7199,3783,5066,7487,3285,1084,8985,760,872,8609,8051,1134,9536,5750,9716,9371,7619,5617,275,9721,2997,2698,1887,8825,6372,3014,2113,7122,7050,6775,5948,2758,1219,3539,348,7989,2735,9862,1263,8089,6401,9462,3168,2758,3748,5870
    :
5304,5499,564,2801,679,2653,1783,3608,7359,7797,3284,796,3222,437,7185,6135,8571,2778,7488,5746,678,6140,861,7750,803,9859,9918,2425,3734,2698,9005,4864,9818,6743,2475,132,9486,3825,5472,919,292,4411,7213,7699,6435,9019,6769,1388,802,2124,1345,8493,9487,8558,7061,8777,8833,2427,2238,5409,4957,8503,3171,7622,5779,6145,2417,5873,5563,5693,9574,9491,1937,7384,4563,6842,5432,2751,3406,7981</>.toString();
}
}

 |