You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Solution
求最短路径，且路径长度是该路径中最大的高度差的绝对值。我们用 /(priority/_queue/), 数组 /(vis[i][j]/) 用来存储从原点到 /(i,j/) 的最短距离。所以在更新时：
/[vis[nx][ny]=/max(vis[x][y], |h[x][y]-h[nx][ny]|)
/]
然后将新的点 /(push/) 到优先队列里面
点击查看代码
class Solution {
private:
int dir[4][2] = {
1,0,
0,1,
-1,0,
0,-1
};
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>> > pq;
vector<vector<int>> vis;
bool check(int x,int y,int r,int c){
if(x<0||y<0||x>=r||y>=c)return false;
return true;
}
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int r = heights.size(), c = heights[0].size();
vis = vector<vector<int>>(r, vector<int>(c,INT_MAX));
pq.push({0,0,0});
vis[0][0]=0;
while(!pq.empty()){
auto f = pq.top();pq.pop();
int x = f[1], y = f[2];
int sp = f[0];
for(int i=0;i<4;i++){
int nx = x+dir[i][0];
int ny = y+dir[i][1];
if(check(nx,ny,r,c) && vis[nx][ny]>max(sp,abs(heights[x][y]-heights[nx][ny]))){
vis[nx][ny] = max(sp, abs(heights[x][y]-heights[nx][ny]));
pq.push({vis[nx][ny],nx,ny});
}
}
}
return vis[r-1][c-1];
}
};
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/288395.html