leetcode 1631. 最小体力消耗路径

张开发
• 2026/4/10 6:37:18 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

leetcode 1631. 最小体力消耗路径
Problem: 1631. 最小体力消耗路径Dijkstra算法矩阵变成1d向量然后初始化状态数组初始化距离数组然后使用优先队列存入距离和当前索引zx * n zy所以可以根据题意上下左右分别connect使用Dijkstra算法求出当前路径差值最大值以及所有路径最大值的最小值Codeusing pr pairint, int; class Solution { public: int dir[4][2] {{-1,0},{1,0},{0,1},{0,-1}}, m, n, m1, n1; int minimumEffortPath(vectorvectorint heights) { m heights.size(), n heights[0].size(); vectorbool sta(m*n, false); priority_queuepr, vectorpr, decltype(greaterpr()) pq; vectorint dis(m * n, INT_MAX); pq.push({0, 0}); dis[0] 0; int x, y, xy, d, zx, zy, zxy, dif; while(!pq.empty()) { d pq.top().first; xy pq.top().second; x xy / n; y xy % n; pq.pop(); if(sta[xy]) continue; sta[xy] true; for(int i 0; i 4; i) { zx x dir[i][0]; zy y dir[i][1]; zxy zx * n zy; if(zx0zy0zxmzyn sta[zxy]false) { dif abs(heights[x][y] - heights[zx][zy]); if(max(dif, d) dis[zxy]) { dis[zxy] max(dif, d); pq.push({dis[zxy], zxy}); } } } } return dis.back(); } };

更多文章