PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 82 / 経路の和:3方向

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

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

今, 31Kのテキストファイル matrix.txt には80×80の行列が書かれている。一番左の行から一番右の行へ移動する際の一番小さなパスの和を求めよ。

Problem 82 - Project Euler


第81問などの類題です。3方向に動けるとかなり自由度が高くなります。

variee.hatenadiary.com

たとえば上から2行目,右から2個目の 422 から出発する場合,5通りの移動ができます。

  • 2つ上がってから右
  • 1つ上がってから右
  • すぐに右
  • 1つ下がってから右
  • 2つ下がってから右

最初は第81問と同じように解こうとしたのですが,最終的に「i 行目から k 行目に移動してから右」の Min をとることに落ちつきました。