c++ - Find optimal route in farm land-dynamic programming/Dijkstra的

Question

我试图在 InterviewStreet 上解决一个问题(比赛已经结束)。问题是在给定 N*M 高程网格的情况下，从池塘到农场 build 一条沟渠。池塘和农场是 N*M 网格中的一个方 block ，不会是同一个方 block 。

海拔是 0 到 9 之间的数字。此外，您还获得了池塘和农场的坐标(1 索引，行后是列)，它们分别占据网格上的一个方 block 。你要编写一个程序，根据这些数据计算 build 一条灌溉沟渠的最低成本。

更具体地说，输入程序的输入格式如下:

NM

池塘位置X 池塘位置Y

农场位置 X 农场位置 Y

海拔X1Y1海拔X1Y2 ...海拔X1YM

海拔X2Y1海拔X2Y2...海拔X2YM

.

.

.

elevationXNY1elevationXNY2...elevationXNYM

其中pondLocationX和farmLocationX为区间[1, N]内的整数，pondLocationY和farmLocationY为区间[1, M]内的整数，所有元素均为区间[0, 9]内的整数。请注意，单个空格将农场和池塘的 X 和 Y 坐标分隔开，但没有空格分隔高程。

给定这样的输入，您的程序应该打印出从池塘到农场 build 一条灌溉沟渠的最低成本。约束条件如下。池塘和农场不会在同一个位置。除池塘外的所有瓷砖的高度都可以增加或减少，每改变一个单位的成本为 1(您可以保持高度不变，成本为 0)。 N 和 M 各最多为 300。在支付任何必要的挖掘费用后，如果有一系列从池塘开始到农场结束的地 block ，则可以以 0 的额外成本 build 一条沟渠，从而满足以下条件: :

1. (连续路径)序列中的每个图 block 都与前一个图 block 相邻(没有对角线邻接—— map 内部的图 block 恰好有 4 个相邻的图 block )

2. (下坡路径)序列中的每个图 block (包括池塘和农场)的高度最多为序列中前一个图 block 的高度。

例如，如果输入如下:

3 5

1 1

3 4

27310

21171

77721

然后我们可以只花费 4 build 一个灌溉沟渠，因为它足以将位置 (1, 3) 的瓦片从 3 降低到 1(成本 2)，然后升高位置 (1, 5) 的瓦片从 0 到 1(成本 1)，并降低位于位置 (3, 4) 的农场，从 2 到 1(成本 1)。请注意，您不能一次从 (2, 3) 到 (3, 4) 沿对角线移动。

解决方法:

我认为这是 Djikstra 算法的一种变体，即使用农场作为源节点，并在计算到池塘的最短路径时停止。 “相邻”的瓷砖是你的邻居，你的边缘权重是你的海拔差异。

但是，由于您可以通过两种方式修改权重，即如果您比您的邻居高，那么您可以 1) 降低您的高度以与您的邻居相匹配或 2) 增加您邻居的高度以与您的相匹配。这种效果可以向外渗透，我无法在算法中捕捉到这一点。

我如何调整 Djikstra 的算法以适应权重可以更改的事实？

Answer 1

在 N*M*10 的 3D 网格上使用 Dijkstra 算法。如果 (x,y) 和 (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 值。

所以您找到的路径就是给定问题的解决方案。