C++ 栈溢出错误分析：最小努力路径问题代码解析

这段代码会导致栈溢出是因为在第二层循环中，循环条件错误，应该是 j < col - 1 而不是 i < col - 1。

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+1, vector<Node>());
        vector<int> minCost = vector<int>(row*col+1, INT_MAX);
        //除开最后一行 最后一列
        for (int i = 0; i < row - 1; ++i) {
            for (int j = 0; j < col - 1; ++j) { // 这里应该是 j < col - 1
                int id = i * row + j;
                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;
            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 * 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;
    }
};

由于 i 是行索引，而 col 是列数，所以 i < col - 1 的判断条件是错误的，应该是 j < col - 1。这个错误会导致 j 的值一直为 0，从而导致第二层循环无法退出，最终导致栈溢出。

修改后的代码：

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+1, vector<Node>());
        vector<int> minCost = vector<int>(row*col+1, INT_MAX);
        //除开最后一行 最后一列
        for (int i = 0; i < row - 1; ++i) {
            for (int j = 0; j < col - 1; ++j) { // 这里应该是 j < col - 1
                int id = i * row + j;
                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;
            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 * 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;
    }
};

修改后的代码修正了循环条件，避免了无限循环，从而解决了栈溢出问题。

希望这个分析能帮助你理解代码错误的原因，并学会如何调试类似的问题。