Problem 82

Path Sum: Three Ways

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

The minimal path sum in the $5$ by $5$ matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to $994$ .

$(\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 left column to the right column in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing a $80$ by $80$ matrix.

路径和：三个方向

注意：本题是第81题的升级版。

在如下的 $5 \times 5$ 矩阵中，从最左栏任意一格出发，始终只向右、向上或向下移动，到最右栏任意一格结束的最小路径和为 $994$ ，由标注红色的路径给出。

$(\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$ 的矩阵，求从该矩阵的最左栏到最右栏的最小路径和。