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

由于一条路径耗费的体力值是路径上相邻牛之间高度差绝对值的最大值，因此遍历时高度差绝对值会越变越大呈单调递增的趋势，符合Dijkstra算法的基本想法

class Solution {
private:
    struct State
    {
        int x;
        int y;
        int maxHeight;
        State(int i, int j, int height)
        {
            this -> x = i;
            this -> y = j;
            this -> maxHeight = height;
        }
    };
    vector<pair<int, int>> getNeig(int i, int j, int m, int n)
    {
        vector<pair<int, int>> Neig;
        if(i - 1 >= 0)
        Neig.push_back({i - 1, j});
        if(i + 1 < m)
        Neig.push_back({i + 1, j});
        if(j - 1 >= 0)
        Neig.push_back({i, j - 1});
        if(j + 1 < n)
        Neig.push_back({i, j + 1});
        return Neig;
    }
    vector<vector<int>> vecmaxH;
public:
    int minimumEffortPath(vector<vector<int> >& heights) {
        int row = heights.size();
        int column = heights[0].size();
        vecmaxH.resize(row, vector<int>(column, INT_MAX));
        priority_queue<State, vector<State>, function<bool(State &, State &)>> pq([](State &a, State &b){return a.maxHeight > b.maxHeight;});
        vecmaxH[0][0] = 0;
        pq.push(State(0, 0, 0));
        while(!pq.empty())
        {
            State cur = pq.top();
            pq.pop();
            int i = cur.x;
            int j = cur.y;
            int maxH = cur.maxHeight;
            if(i == row - 1 && j == column - 1)
            return maxH;
            if(maxH > vecmaxH[i][j])
            continue;
            for(auto neig : getNeig(i, j, row, column))
            {
                int next_i = neig.first;
                int next_j = neig.second;
                int next_maxH = max(abs(heights[next_i][next_j] - heights[i][j]), maxH);
                if(vecmaxH[next_i][next_j] > next_maxH)
                vecmaxH[next_i][next_j] = next_maxH;
                pq.push(State(next_i, next_j, next_maxH));
            }
        }
        return -1;
    }
};