题解 | #牛群的最小体力消耗值#

类似Dijkstra算法，找出所有可行路径中代价最少的那一条，朝四个方向移动， 计算其代价，更新每个点的minCost， 并加在队列后面，依次进行，最后取出重点的minCost。

#include <queue>
#include <cstring> // for memset

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param heights int整型vector<vector<>>
     * @return int整型
     */
    static const int maxn = 1e2 + 5;

    struct node {
        int x;
        int y;
        int val;
    };

    struct cmp {
        bool operator()(node a, node b) {
            return a.val > b.val; // 优先队列按照 val 的升序排序
        }
    };

    int minimumEffortPath(vector<vector<int>>& heights) {
        int n = heights.size(); // 矩阵的行数
        int m = heights[0].size(); // 矩阵的列数
        int minCost[maxn][maxn];
        
        memset(minCost, 0x3f, sizeof(minCost)); // 初始化 minCost 数组为最大值

        int dx[] = {1, 0, -1, 0}; // 方向数组，分别表示下、右、上、左
        int dy[] = {0, 1, 0, -1};

        priority_queue<node, vector<node>, cmp> pq;
        pq.push({0, 0, 0}); // 起点位置入队，初始耗费值为 0

        while (!pq.empty()) {
            node t = pq.top();
            pq.pop();

            for (int i = 0; i < 4; i++) {
                int xx = t.x + dx[i];
                int yy = t.y + dy[i];

                if (xx >= 0 && xx < n && yy >= 0 && yy < m) { // 判断新位置是否在矩阵范围内
                    int update = max(t.val, abs(heights[xx][yy] - heights[t.x][t.y])); // 计算从当前位置到新位置的耗费值（取当前耗费值和高度差的最大值）
                    
                    if (update < minCost[xx][yy]) { // 如果新位置的耗费值更小，则更新最小耗费值，并将新位置加入优先队列
                        minCost[xx][yy] = update;
                        pq.push({xx, yy, minCost[xx][yy]});
                    }
                }
            }
        }

        return minCost[n - 1][m - 1]; // 返回终点的最小耗费值
    }
};