二维阵列中的最小上升和下降量 [英] minimum amount of ascent and descent in 2d array

问题描述

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

I have a 2D array of numbers, my task is to find minimum amount of ascent or descent from starting index [0,0] to the end index.

约束是我们不应该斜行。

The constraint is we should not travel diagonally.

示例：

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

解决此问题的方法是什么？

What is the approach to solving this problem?

更新：

我使用了 Dijstra算法代码通过我的输入2D数组，并且我设置了 V = 3 因为我的数组有3行，所以不确定我是否正确设置了V值。

I have used Dijstra algorithm code to pass my input 2D array and I have set V=3 as my array has 3 rows, not sure if I have set my V value correctly.

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

The 2D array I have set in code is :

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

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

Then the program gave me below result:

Vertex       Distance from Source
0        0
1        2
2        3

我无法理解此结果指示的内容以及它与我的问题陈述的关系。

I am not able to understand what this result indicates, and how it relates to my problem statement.

推荐答案

您的问题转化为在图中找到最短路径的地方，其中数字是节点，并且加权的双向边缘水平和垂直地连接了邻居。每个边缘的权重或距离是上升或下降（如@jhamon所说）。因此，您的图形变为：

Your problem translates to finding the shortest path in a graph where your numbers are the nodes and weighted, bidirectional edges connect neighbours horizontally and vertically. The weight or distance for each edge is the ascent or descent (as @jhamon said). So your graph becomes:

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

请注意，某些边的权重为0，

Note that some edges have weight 0, that is, are traveled for free.

因此，请查找一种算法，以找到图中的最短路径。 Dijkstra的算法是显而易见的选择。

So look up an algorithm for finding the shortest path in a graph. Dijkstra’s algorithm is the obvious choice.

或者说清楚一点：您的程序将依次执行两个步骤：

Or to spell it out just a little bit more: Your program will perform two steps after each other:

1. 将矩阵转换为图形，其中节点之间的距离为上升/下降。从样本3 x 3数组中，您将得到一个具有9个节点和12条边的图形。


2. 运行Dijkstra算法，查找距起始节点（索引[0生成的节点] ，0]）移至图形的每个其他节点。这还将确保计算到末端的距离。此距离是上升或下降的最小距离。

链接： Dijkstra最短路径算法| GeeksforGeeks上的Greedy Algo-7

这篇关于二维阵列中的最小上升和下降量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！