Wegsumme: vier Richtungen

Problem 83

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

Die minimale Wegsumme in der 5×5-Matrix unten von der oberen linken zur unteren rechten Ecke - man bewegt sich immer nach links, rechts, oben oder unten - ist dick und rot dargestellt und beträgt 2297.

$\begin{pmatrix} \color{red}{131} & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & \color{red}{150}\\ 630 & 803 & 746 & \color{red}{422} & \color{red}{111}\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{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 oberen linken zur unteren rechten Ecke, indem immer nach links, rechts, oben oder unten bewegt wird.

Diese Übersetzung wurde von Philipp Fischbeck erstellt.

Dieses Problem auf projecteuler.net