C++ 最小体力消耗路径算法优化与错误分析

这段代码旨在使用 Dijkstra 算法求解最小体力消耗路径问题。代码中存在以下三个错误：

1. 第10行应该是 int id = i * col + j;，而不是 int id = i * row + j;，因为矩阵的列数是 col，而不是行数 row。

2. 第47行的判断条件应该是 if (nd.id == target)，而不是赋值操作 if (nd.id = target)。

3. 第56行的判断条件应该是 if (weight < minCost[neighbour.id])，而不是 if (weight > minCost[neighbour.id])，因为要求的是最小代价路径。

以下是修正后的代码：

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 * col + j; // 修正错误
                // cout << id << " " <<  i << " " << j << endl;
                int des1 = i * col + j + 1;
                int cost1 = abs(heights[i][j+1] - heights[i][j]);
                int des2 = (i + 1) * col + 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 * col + col - 1; // 修正错误
            // cout << id << " " << j << endl;
            int des = id + col; // 修正错误
            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;
    }
};

这段代码使用Dijkstra算法寻找从起点到终点的最小体力消耗路径，代码中包含对矩阵索引的修正，判断条件的修正以及逻辑的修正。

希望这篇文章对大家理解最小体力消耗路径算法以及C++代码调试有所帮助。