Wegsumme: drei Richtungen

Problem 82

HINWEIS: Dieses Problem ist eine schwierigere Version von Problem 81.

Die minimale Wegsumme in der 5×5-Matrix unten - man beginnt in einer beliebigen Zelle der linken Spalte und endet in einer beliebigen Zelle der rechten Spalte und bewegt sich nur nach oben, nach unten oder nach rechts - ist dick und rot markiert; die Summe ist 994.

$\begin{pmatrix} 131 & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & 746 & 422 & 111\\ 537 & 699 & 497 & 121 & 956\\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}$

Finden Sie die minimale Wegsumme in matrix.txt (Rechtsklick und "Link/Ziel speichern unter..."), einer 31K Textdatei, die eine 80×80-Matrix enthält, von der linken zur rechten Spalte.

Diese Übersetzung wurde von Philipp Fischbeck erstellt.

Dieses Problem auf projecteuler.net