我正在尝试解决有关InterviewStreet的问题(比赛已经结束)。问题是，给定N * M的高程网格，从池塘到农场建一条沟。池塘和农场是N * M网格中的图块之一，不会是同一个图块。
高程是介于0到9之间的数字。此外，还为您提供了池塘和农场的坐标(1索引，行后跟列)，每个坐标仅占据网格上的一个图块。您将要编写一个程序，给定此数据，该程序将计算建造灌溉沟渠的最低成本。
更具体地说，将输入到程序中的输入的格式如下:
牛顿
池塘位置X池塘位置Y
farmLocationX farmLocationY
海拔X1Y1海拔X1Y2 ...海拔X1YM
高程X2Y1高程X2Y2 ...高程X2YM
。
。
。
高程XNY1高程XNY2 ...高程XNYM
其中poolLocationX和farmLocationX是间隔[1，N]中的整数，而poolLocationY和farmLocationY是间隔[1，M]中的整数，所有元素都是间隔[0，9]中的整数。请注意，单个空间分隔了农场和池塘的X和Y坐标，但是没有分隔高程的空间。
有了这样的输入，您的程序应打印出从池塘到农场建造灌溉沟渠的最低成本。约束如下。池塘和农场将不在同一地点。除池塘外，所有图块的高程可以每更改一个单位增加或减少一个成本(您可以将高程保持不变，但成本为0)。 N和M最多为300。支付必要的挖掘费用后，如果有一系列从瓷砖开始到农场结束的瓷砖，您可以以0的额外费用建造一个沟渠，以确保满足以下条件: :
例如，如果输入如下:
3 5
1 1
3 4
27310
21171
77721
那么我们可以以4的成本建造一个灌溉沟，因为它足以将位置(1、3)的瓷砖从3降低到1(成本2)，将位置(1、5)的瓷砖从0提升到1(成本1)，然后将位置(3，4)的服务器场从2降为1(成本1)。请注意，您不能对角地一步一步地从(2，3)到达(3，4)。
解:
我认为这是Djikstra算法的一种变体，即使用农场作为源节点，并在计算到池塘的最短路径时停止。 “相邻”图块是您的邻居，边缘权重是您的高程的差。
但是，由于您可以通过两种方式修改权重，即，如果您的体重比邻居高，那么您可以1)降低高度以匹配邻居的高度，或者2)增加邻居的高度以匹配您的高度。这种效果可以向外渗透，我无法在算法中捕获。
如何调整Djikstra的算法以适应权重可以更改的事实？
最佳答案
在3D网格N * M * 10上使用Dijkstra算法。如果(x，y)和(x'，y')相邻且z'不大，则两个顶点(x，y，z)和(x'，y'，z')连接在一起(具有定向弧)比z弧上的成本由z'和(x'，y')处的初始高度之差给出。然后找到从池塘(具有其初始长度)到农场的最短路径(即使z坐标不同)。
用这种方法找到的最小路径有可能在同一点(x，y)上经过两次。例如，它可以首先从(x，y，z')通过，然后从(x，y，z'')通过。但是如果发生这种情况，您可以删除从(x，y，z')到(x，y，z'')的路径，因为用(x，y，z'')替换(x，y，z')的成本相等或小于从(x，y，z')到(x，y，z'')的路径。因此，您可以假设路径的每个点(x，y)仅使用z的单个值。
因此，您找到的路径就是解决给定问题的方法。