我正在 LeetCode.com 上解決這個名為
我的代碼是：
class Solution {
public:
vector<pair<int,int>> getNeighbors(vector<vector<int>>& h, int r, int c) {
vector<pair<int,int>> n;
if(r 1<h.size()) n.push_back({r 1,c});
if(c 1<h[0].size()) n.push_back({r,c 1});
if(r-1>=0) n.push_back({r-1,c});
if(c-1>=0) n.push_back({r,c-1});
return n;
}
int minimumEffortPath(vector<vector<int>>& heights) {
int rows=heights.size(), cols=heights[0].size();
using arr=array<int, 3>;
priority_queue<arr, vector<arr>, greater<arr>> pq;
vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
pq.push({0,0,0}); //r,c,weight
dist[0][0]=0;
//Dijkstra
while(pq.size()) {
auto [r,c,wt]=pq.top();
pq.pop();
if(wt>dist[r][c]) continue;
vector<pair<int,int>> neighbors=getNeighbors(heights, r, c);
for(auto n: neighbors) {
int u=n.first, v=n.second;
int curr_cost=abs(heights[u][v]-heights[r][c]);
if(dist[u][v]>max(curr_cost,wt)) {
dist[u][v]=max(curr_cost,wt);
pq.push({u,v,dist[u][v]});
}
}
}
return dist[rows-1][cols-1];
}
};
這被接受了，但我有兩個問題：
a. Since we update dist[u][v] if it is greater than max(curr_cost,wt), how does it guarantee that in the end we return the minimum effort required? That is, why don't we end up returning the effort of the one in red above?
b. Some solutions such as this one, short-circuit and return immediately when we reach the bottom right the first time (ie, if(r==rows-1 and c==cols-1) return wt;) - how does this work? Can't we possibly get a shorter dist when we revisit the bottom right node in future?
uj5u.com熱心網友回復：
問題陳述要求我們找到“努力”最少的路徑。
“努力”定義為路徑上相鄰單元格之間的最大高度差。
該運算式max(curr_cost, wt)處理問題陳述的最大部分。當從一個單元格移動到另一個單元格時，到新單元格的距離要么與到舊單元格的距離相同，要么是高度差，以較大者為準。因此max(difference_in_heights, distance_to_old_cell)。
Dijkstra 的演算法處理問題陳述的最小部分，其中我們使用從起始節點到任何給定節點所需的“努力”，而不是使用與起始節點的距離。Dijkstra 試圖最小化距離，因此它最小化了作業量。
Dijkstra 有兩個密切相關的概念：visited和explored。當使用任何傳入邊到達節點時，將訪問該節點。當一個節點的出邊被用來訪問它的鄰居時，它就會被探索。Dijkstra 的關鍵設計特征是在探索了一個節點之后，對該節點的額外訪問永遠不會增加到該節點的距離。這就是優先佇列的原因。優先級佇列保證被探索的節點在所有未探索節點中距離最小。
在示例網格中，紅色路徑將在綠色路徑之前被探索，因為紅色路徑在最后一步之前有努力 1，而綠色路徑有努力 2。所以紅色路徑會將到右下角單元格的距離設定為 3 ，即dist[2][2] = 3。
但是當探索綠色路徑時，我們在 row=2, col=1 處到達 3，我們有
- 距離[2][2] = 3
- curr_cost=2
- 重量=2
所以dist[2][2] > max(curr_cost, wt)， 和dist[2][2]減少到 2。
問題的答案：
一種。紅色路徑暫時將右下角單元格的距離設定為 3。但是紅色路徑的結果被丟棄，取而代之的是綠色路徑的結果。這是 Dijkstra 演算法搜索最小值的自然結果。
灣 當右下節點準備好被探索時，即它位于優先級佇列的頭部，那么它就有了它所擁有的最佳距離，因此演算法可以在那個點停止。這也是 Dijkstra 演算法的自然結果。優先級佇列保證在一個節點被探索之后，以后對該節點的訪問不會減少它的距離。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313566.html