2d阵列的最小上升和下降量

Question

我有一个二维的数字数组，我的任务是找到从起始索引0,0到结束索引的最小上升或下降量。

制约因素是我们不应该以对角线旅行。

示例：

1 2 3
1 2 0
6 3 2

解决方案：

Path --> 1 -> 1 -> 2 -> 3 -> 2.
1-1 = 0
2-1 = 1
3-2 = 1
3-2 = 1

Result = 0 + 1 + 1 + 1 = 3

解决这个问题的方法是什么？

更新：

我使用Dijstra算法代码传递输入的2D数组，并将V=3设置为数组有3行，不确定是否正确设置了V值。

我在代码中设置的2D数组是：

int graph[][] = new int[][] {{1,2,3}, {1,2,0},{6,3,2}};

然后程序给了我以下结果：

Vertex       Distance from Source
0        0
1        2
2        3

我无法理解这个结果表明了什么，以及它与我的问题陈述有什么关系。

Answer 1

您的问题转化为在图中找到最短路径，其中您的数字是节点和加权，双向边连接相邻水平和垂直。每个边缘的重量或距离是上升或下降(如@jhamon所说)。所以你的图表变成：

1 -1- 2 -1- 3
|     |     |
0     0     3
|     |     |
1 -1- 2 -2- 0
|     |     |
5     1     2
|     |     |
6 -3- 3 -1- 2

请注意，一些边的重量为0，也就是说，是免费的。

所以，找出图中最短路径的算法。Dijkstra算法是最明显的选择。

或者再说几句:您的程序将在后面执行两个步骤：

1. 将你的矩阵转换成一个图，其中节点之间的距离是上升/下降。从您的示例3×3数组中，您将得到一个有9个节点和12个边的图。
2. 运行Dijkstra算法，找到从起始节点(从索引0，0生成的节点)到图的每个其他节点的最短距离。这还将确保计算到终点的距离。这个距离是上升或下降的最小幅度。

链接： Dijkstra的最短路径算法--贪婪Algo-7 on GeeksforGeeks