InterviewStreet で質問を解こうとしていました (コンテストは終了しました)。問題は、標高の N*M グリッドが与えられた場合に、池から農場までの溝を作ることです。池と農場は N*M グリッド内のタイルの 1 つであり、同じタイルにはなりません。
標高は 0 ～ 9 の数値です。さらに、池と農場の座標 (1 インデックス、行の後に列が続く) が与えられ、それぞれがグリッド上の正確に 1 つのタイルを占有します。このデータを基に、灌漑用水路を建設するための最小費用を計算するプログラムを作成します。
より具体的には、プログラムに供給される入力は次のようにフォーマットされます。
NM
池の位置 X 池の位置 Y
farmLocationX farmLocationY
標高X1Y1標高X1Y2...標高X1YM
標高X2Y1標高X2Y2...標高X2YM
.
.
.
標高XNY1標高XNY2...標高XNYM
ここで、pondLocationX と farmLocationX は区間 [1, N] の整数で、pondLocationY と farmLocationY は区間 [1, M] の整数で、すべての要素は区間 [0, 9] の整数です。農場と池の X 座標と Y 座標は 1 つのスペースで区切られていますが、高さを区切るスペースはありません。
このような入力が与えられた場合、プログラムは、池から農場までの灌漑用水路を建設するための最小コストを出力する必要があります。制約は次のとおりです。池と農場は同じ場所にはありません。池を除くすべてのタイルの標高は、変更単位ごとに 1 のコストで増減できます (コスト 0 で標高を同じままにすることができます)。N と M はそれぞれ最大で 300 です。必要な掘削費用を支払った後、次の条件を満たすタイルが池から始まり農場で終わる場合、追加コスト 0 で溝を作ることができます。 :
(連続したパス) シーケンス内の各タイルは前のタイルに隣接しています (対角隣接関係はありません -- マップの内側のタイルには、ちょうど 4 つの隣接するタイルがあります)。
(下り坂) 池と農場を含むシーケンス内の各タイルの高さは、シーケンス内の前のタイルの高さ以下です。
たとえば、入力が次の場合:
3 5
1 1
3 4
27310
21171
77721
次に、位置 (1, 3) のタイルを 3 から 1 に下げ (コスト 2)、位置 (1, 5) のタイルを 0 から1 (コスト 1)、場所 (3, 4) にある農場を 2 から 1 (コスト 1) に下げます。1 ステップで (2, 3) から (3, 4) に到達するために斜めに移動することはできないことに注意してください。
解決：
これはジクストラのアルゴリズムのバリエーションだと思います。つまり、ファームをソース ノードとして使用し、池までの最短経路を計算すると停止します。「隣接する」タイルは隣人であり、エッジの重みは高さの違いです。
ただし、重みは 2 つの方法で変更できるため、隣人よりも背が高い場合は、1) 隣人の身長に合わせて身長を下げるか、2) 隣人の身長に合わせて隣人の身長を高くすることができます。この効果は外側に浸透する可能性があり、アルゴリズムでこれを捉えることができません。
重みを変更できるという事実に対応するために、Djikstra のアルゴリズムを調整するにはどうすればよいですか?