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.
| 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 |
Find the minimal path sum, in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.
路径和：三个方向
注意：这是第81题的一个更具挑战性的版本。
在如下的5乘5矩阵中，从最左栏任意一格出发，始终只向右、向上或向下移动，到最右栏任意一格结束的最小路径和为994，由标注红色的路径给出。
| 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 |
在这个31K的文本文件matrix.txt（右击并选择“目标另存为……”）中包含了一个80乘80的矩阵，求出从最左栏到最右栏的最小路径和。