时间戳

首页 > 解决方案 > 二维数组中的最小上升和下降量

java - 二维数组中的最小上升和下降量

问题描述

我有一个二维数字数组，我的任务是找到从起始索引 [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 算法代码来传递我的输入二维数组，并且我已经设置V=3为我的数组有 3 行，不确定我是否正确设置了我的 V 值。

我在代码中设置的二维数组是：

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

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

Vertex       Distance from Source
0        0
1        2
2        3

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

标签： javaalgorithm

解决方案

您的问题转化为在图中找到最短路径，其中您的数字是节点，加权的双向边水平和垂直连接邻居。每个边缘的权重或距离是上升或下降（如@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 x 3 数组中，您将获得一个包含 9 个节点和 12 条边的图。
  2. 运行 Dijkstra 算法以找到从起始节点（从索引 [0, 0] 生成的节点）到图的每个其他节点的最短距离。这也将确保计算到终点的距离。这个距离是上升或下降的最小量。

链接： Dijkstra 的最短路径算法 | GeeksforGeeks 上的贪婪算法 7

推荐阅读