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

本文主要是介绍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];}
};