Problem 83

Path Sum: Four Ways

NOTE: This problem is a significantly more challenging version of Problem 81.

In the $5$ by $5$ matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to $2297$ .

$(\begin{matrix} 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 \end{matrix})$

Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing a $80$ by $80$ matrix.

路径和：四个方向

注意：这是第81题的究极升级版。

在如下的 $5 \times 5$ 矩阵中，从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和为 $2297$ ，由标注红色的路径给出。

$(\begin{matrix} 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 \end{matrix})$

在文本文件matrix.txt中包含了一个 $80 \times 80$ 的矩阵，求从该矩阵的左上角到右下角任意地向上、向下、向左或向右移动的最小路径和。