C++ 最小努力路径算法优化：解决节点 ID 计算错误

这段代码的 bug 在于计算节点 id 时有误，应为 i * col + j 而不是 i * row + j。

以下是修正后的代码：

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; // 修正后的节点 ID 计算
                // 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; // 修正后的节点 ID 计算
                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; // 修正后的节点 ID 计算
            // cout << id << ' ' << j << endl;
            int des = id + col; // 修正后的节点 ID 计算
            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; // 修正后的节点 ID 计算
            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;
    }
};

解释：

• 代码中使用 i * row + j 来计算节点 ID，这会导致错误的节点映射。
• 正确的计算方式应为 i * col + j，因为每个节点的 ID 应由其在矩阵中的行号和列号决定，而 row 对应的是矩阵的行数，col 对应的是矩阵的列数。

修正后的代码中，所有节点 ID 计算都使用了 i * col + j 的公式，保证了节点 ID 的正确映射，从而解决了代码中的 bug。

总结：

在使用算法解决矩阵问题时，一定要仔细检查节点 ID 的计算方法，避免出现类似错误，导致算法无法正常工作。