我试图在 InterviewStreet 上解决一个问题（比赛已经结束）。问题是在给定 N*M 网格高程的情况下，从池塘到农场建造一条沟渠。池塘和农场是 N*M 网格中的一个图块，不会是同一个图块。
高程是 0 到 9 之间的数字。此外，您还会获得池塘和农场的坐标（1 索引，行后列），每个坐标都恰好占据网格上的一个图块。你要编写一个程序，给定这些数据，计算建造灌溉渠的最低成本。
更具体地说，将输入到您的程序中的输入将被格式化如下：
纳米
池塘位置X 池塘位置Y
农场位置X 农场位置Y
海拔X1Y1海拔X1Y2...海拔X1YM
海拔X2Y1海拔X2Y2...海拔X2YM
.
.
.
海拔XNY1海拔XNY2...海拔XNYM
其中，pondLocationX和farmLocationX为区间[1, N]内的整数，poolLocationY和farmLocationY为区间[1, M]内的整数，所有元素均为区间[0, 9]内的整数。请注意，农场和池塘的 X 和 Y 坐标用一个空格分隔，但高程之间没有空格。
给定这样的输入，您的程序应该打印出从池塘到农场建造灌溉沟的最低成本。约束如下。池塘和农场将不在同一位置。除池塘外的所有图块的标高都可以增加或减少，每改变一个单位的成本为一个（您可以将标高保持不变，但成本为 0）。N 和 M 最多为 300。在支付任何必要的挖掘费用后，如果有一系列瓷砖从池塘开始到农场结束，那么您可以以 0 额外费用建造一条沟渠，并且满足以下条件：
（连续路径）序列中的每个图块都与前一个图块相邻（无对角邻接——地图内部的图块恰好有 4 个相邻图块）
（下坡路径）序列中的每个图块，包括池塘和农场，都具有最多为序列中前一个图块的高度。
例如，如果输入如下：
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 的算法以适应权重可以更改的事实？