给定两个坐标计算矩阵中最快距离的 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 algorithm 的算法。寻找最短路径。

您可以先将您的矩阵转换为图形数据结构(例如邻接矩阵):矩阵的每个元素都是一个顶点，元素的值是边成本。垂直或水平相邻的元素之间只有边，在这种情况下，这也将是一个有向图。

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 算法实现，您可以自己实现，也可以在网络上轻松找到它。

提示:如果需要求路径的值(如上所说)，也可以将第一个和最后一个元素的值保存起来，与算法。