LeetCode每日一题 | 最小体力消耗路径（C++）

1. 题目描述

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2 解释：路径 [1,3,5,3,5]
连续格子的差值绝对值最大为 2 。 这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

输入：heights =[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-minimum-effort
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

首先看到题目想到是用动态规划，但是由于线路并非简单的向下、向右的选择，可以出现向上的情况，因此无法根据上一个状态来推算出下一个状态的解，便无法使用动态规划算法。

2.1 Dijkstra算法

将[0][0]作为源点，利用dijkstra算法求到终点的最短路径长度。（此处参考了零神的题解QAQ）

struct Dist{int x,y,z;Dist(int _x,int _y,int _z):x(_x),y(_y),z(_z){}bool operator< (const Dist& that) const{//队列优先规则return z>that.z;//小顶堆}};
class Solution {
private:static constexpr int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};//代表上下左右四个方向public:int minimumEffortPath(vector<vector<int>>& heights) {int rows = heights.size();//长int columns = heights[0].size();//宽priority_queue<Dist> q;//优先队列，以z值小的优先，即距离近的优先q.emplace(0,0,0);vector<int> seen(rows*columns);vector<int> dist(rows*columns,INT_MAX);//每个元素均为最大值dist[0]=0;while(!q.empty()){auto [x,y,z] = q.top();//取出当前距离最近的点q.pop();//弹出if(seen[x*columns+y])continue;seen[x*columns+y]=1;dist[x*columns+y]=z;//保存远点到选中点距离for(int i=0;i<4;i++){int nx = x+dirs[i][0];int ny = y+dirs[i][1];if(nx>=0 && nx<rows && ny>=0 && ny<columns && !seen[nx*columns+ny]){q.emplace(nx,ny,max(z,abs(heights[nx][ny]-heights[x][y])));//以选出的最近点作为中转点}}}return dist[rows*columns-1];}
};

运行结果如下图所示：