使用Dijkstra算法求解二维矩阵中的最小努力路径

这是一道最短路径问题，考虑使用Dijkstra算法来解决。

首先，我们将二维矩阵转化为一维图，每个格子对应一个节点，每个节点与其上下左右相邻的节点之间连一条有向边，边的权值为相邻两个格子的高度差的绝对值。

接下来，我们从起点开始，使用Dijkstra算法求解最短路径。具体来说，我们维护一个最小堆，每次从堆中取出当前距离起点最近的节点，然后对于该节点的所有相邻节点，如果从起点到该相邻节点的距离比已有的最短距离小，则更新最短距离，并将该相邻节点加入堆中。

当我们找到终点时，返回该节点的距离即可。

时间复杂度

建图的时间复杂度为 $O(mn)$，Dijkstra算法的时间复杂度为 $O(mn\log(mn))$，因此总时间复杂度为 $O(mn\log(mn))$。

空间复杂度

建图的空间复杂度为 $O(mn)$，Dijkstra算法的空间复杂度为 $O(mn)$，因此总空间复杂度为 $O(mn)$。

C++ 代码

struct Node {
    int id;
    int dis;
    Node(int id, int dis) : id(id), dis(dis) {};
    friend bool operator < (Node n1, Node n2) {
        return  n1.dis < n2.dis;
    }
};
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int row = heights.size();
        int col = heights[0].size();
        vector<vector<Node>> graph = vector<vector<Node>>(row * col, vector<Node>());
        vector<int> minCost = vector<int>(row*col, INT_MAX);
        //除开最后一行 最后一列
        for (int i = 0; i < row - 1; ++i) {
            for (int j = 0; j < col - 1; ++j) {
                int id = i * row + j;
                // cout << id << ' ' <<  i << ' ' << j << endl;
                int des1 = i * row + j + 1;
                int cost1 = abs(heights[i][j+1] - heights[i][j]);
                int des2 = (i + 1) * row + j;
                int cost2 = abs(heights[i+1][j] - heights[i][j]);
                graph[id].push_back(Node(des1,cost1));
                graph[id].push_back(Node(des2,cost2));
            }
        }
        //最后一列
        for (int j = 0; j < row - 1; j++) {
            int id = j * row + col - 1;
            // cout << id << ' ' << j << endl;
            int des = id + row;
            int cost = abs(heights[j+1][col-1] - heights[j][col-1]);
            graph[id].push_back(Node(des,cost));
        }
        //最后一行
        for (int i = 0; i < col - 1; i++) {
            int id = (row - 1) * col + i;
            int des = id + 1;
            int cost = abs(heights[row-1][i] - heights[row-1][i+1]);
            graph[id].push_back(Node(des,cost));
        }
        int target = row * col - 1;
        priority_queue<Node> q;
        q.push(Node(0,0));
        while (!q.empty()) {
            Node nd = q.top();
            q.pop();
            if (nd.id == target) {
                return nd.dis;
            }
            if (nd.dis > minCost[nd.id]) {
                continue;
            }
            for (auto& neighbour : graph[nd.id]) {
                int weight = neighbour.dis + nd.dis;
                if (weight < minCost[neighbour.id]) {
                    minCost[neighbour.id] = weight;
                    q.push(Node(neighbour.id,weight));
                }
            }
        }
        return INT_MAX;
    }
};