给定两个坐标，如何在矩阵中以Pythonic方式计算最快距离？

Question

举个例子，如果我有一个X乘Y的街道交叉口网格，目标位置在右下角（坐标是x-1,y-1）。那么，给定一个矩阵，怎么计算距离呢？

比如，如果输入的矩阵是：

matrix=[[1,2,1],
        [2,3,2],
        [1,2,1]]

假设我从坐标(0,0)出发，这里是1，想要到达(2,2)，这里也是1，位于右下角。最快的距离是7（向右和向下走）。

你也可以先向右走一步，再向下走，然后再向右走，再向下走。这条路的距离是8：1+2+3+2+1=8。

那么，怎么找到最短的路径呢？你只能向右和向下移动。我想用嵌套的for循环，但不太明白该怎么做才能实现这个逻辑。

Answer 1

我觉得这个问题可以看作是一个图的问题。所以，你可以使用像Dijkstra算法这样的算法来找到最短路径。

你可以先把你的矩阵转换成一个图的数据结构（比如邻接矩阵）：矩阵中的每个元素都是一个点，而元素的值就是边的成本。只有那些上下左右相邻的元素之间才有边，并且在这种情况下，这也是一个有向图。

1 [[0 2 0 2 0 0 0 0 0],
2  [1 0 1 0 3 0 0 0 0],
3  [0 2 0 0 0 2 0 0 0],
4  [1 0 0 0 3 0 1 0 0],
5  [0 2 0 2 0 2 0 2 0],
6  [0 0 1 0 3 0 0 0 1],
7  [0 0 0 2 0 0 0 2 0],
8  [0 0 0 0 3 0 1 0 1],
9  [0 0 0 0 0 2 0 2 0]]

之后，只需要使用Dijkstra算法的实现，你可以自己写一个，或者在网上很容易找到现成的。

提示：如果你需要找到路径的值（就像你上面说的那样），你还可以保存第一个和最后一个元素的值，然后把它们和算法找到的路径值相加。