在如下的$5\times 5$矩阵中，从左上角到右下角、允许向上、下、左、右四个方向移动但不得重复访问单元格的最小路径和为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}$$ 在文件matrix.txt中包含了一个$80 \times 80$的矩阵，求从该矩阵的左上角到右下角、允许向上、下、左、右四个方向移动但不得重复访问单元格的最小路径和。

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

本题难度:

解答

将该矩阵M视为图，矩阵中每个元素$M_{ij}$都是图中的节点，它与其上下左右的相邻元素连通，用Dijkstra算法求最短路径即得结果$425185$。

a=[]
with open("083_matrix.txt") as f:
    for line in f:
        a.append([int(i) for i in line.split(",")])

res={(0,0):a[0][0]}
d={}
for i in range(80):
    for j in range(80):
        d[(i,j)]=-1
d[(0,1)]=a[0][0]+a[0][1]
d[(1,0)]=a[0][0]+a[1][0]
del d[(0,0)]

while d:
    i,j=min([d[k],k] for k in d if d[k]>0)[1]
    res[(i,j)]=d[(i,j)]
    if i>0 and (i-1,j) in d and (d[(i-1,j)] < 0 or d[(i-1,j)]>res[(i,j)]+a[i-1][j]):
            d[(i-1,j)]=res[(i,j)]+a[i-1][j]
    if i < 79 and (i+1,j) in d and (d[(i+1,j)] < 0 or d[(i+1,j)]>res[(i,j)]+a[i+1][j]):
        d[(i+1,j)]=res[(i,j)]+a[i+1][j]
    if j>0 and (i,j-1) in d and (d[(i,j-1)] < 0 or d[(i,j-1)]>res[(i,j)]+a[i][j-1]):
        d[(i,j-1)]=res[(i,j)]+a[i][j-1]
    if j < 79 and (i,j+1) in d and (d[(i,j+1)] < 0 or d[(i,j+1)]>res[(i,j)]+a[i][j+1]):
        d[(i,j+1)]=res[(i,j)]+a[i][j+1]
    del d[(i,j)]
print res[(79,79)]