083. 路径数字之和:四个方向(Path sum: four ways)

在下面这个五乘五的数字矩阵中,从左上角出发,可以向左、右、上、下四个方向走,最后到达右下角,这其中所经过数字之和的最小值是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中有一个八十行八十列的数字矩阵,求从这个矩阵的左上角到右下角的所经数字之和的最小值。

注:这道题比第八十一题更具挑战性。

分析:回忆一下八十一题中我们使用动态规划解决了问题,但由于这道题允许我们往左走,显然不能再用动态规划解题。另外一个思路是就是使用我们之前已经介绍过图论的思想,使用图论的相关算法来解决。我们可以把问题转化成寻找从数字矩阵的左上角到达右下角的最短路径,其中路径的权重为矩阵中的数字。显然,我们可以用著名的迪克斯特拉算法来解决这个图论问题。

在python中我们可以用使用networkx库,其中已经封装好相关的算法,我们只需要把数字矩阵按照networkx库的规则转化成为一个有向加权图,然后调用相关算法计算从矩阵的左上角到右下解的最短路径就可以了。关于这个库的相关用法我不再详述,网上有很多相关的文章。代码如下:

# time cost = 98.2 ms ± 580 µs

import networkx as nx

def main():
    with open('data/pe083.txt') as f:
        matrix = [[int(x) for x in row.split(',')] for row in f.readlines()]
    G = nx.DiGraph()
    for i in range(n):
        for j in range(m):
            neighbors = [(i+x, j+y) for x, y in [(-1,0), (0,-1), (1,0), (0,1)] if 0 <= i+x < n and 0 <= j+y < m]
            for ix, jy in neighbors:
                G.add_edge((i, j), (ix, jy), weight = matrix[ix][jy])
    path_length = nx.dijkstra_path_length(G, source=(0,0), target=(n-1,m-1))
    return path_length + matrix[0][0]