PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 83 / 経路の和:4方向

下記の5次の正方行列で左上のセルから出発して上下左右に移動し,右下のセルで終了する道を探索する。一番小さな道は下で赤で示されており,このときの合計は2297になる。

いま, 31Kのテキストファイル matrix.txt には 80*80 の行列が書かれている。左上のセルから出発して上下左右に移動し,右下のセルで終了する道に沿った和の最小を求めよ。

Problem 83 - Project Euler


問題82では上下右の3方向への移動でしたが,こちらは上下左右4方向への移動です。

variee.hatenadiary.com


グラフ理論で解きます。移動できる方向に辺を作り,各セルの数字をその辺の重みとして定義します。採点距離は GraphDistance で求められます。

と,偉そうに書きましたが,このコードは問題82の正解者掲示板で見たものをちょっといじっただけです*1。おかげでグラフの作り方がよくわかったので,他の問題にも積極的に使っていきたいと思います。

*1:コード中,一部余計な記述がありますが,これは他の問題に流用するときのために残した部分です。