C++回溯算法中嵌套vector访问引发段错误问题求助

核心问题：非法内存访问（数组越界） #

你定位的visited[visited.size()-2]就是段错误的直接诱因，具体原因有两点：

1. 初始状态下visited为空：main函数里初始化的visited是个空容器，第一次调用backtracking时直接进入makeDecision，此时visited.size()为0，计算visited.size()-2得到-2，访问这个下标属于非法内存操作，直接触发段错误。
2. 全程未维护visited的内容：整个回溯逻辑里没有任何代码把当前路径位置存入visited，哪怕递归多次，visited的大小也始终达不到能访问size()-2的要求（至少需要容器内有2个元素）。

修复步骤 #

1. 初始化时记录起点位置 #

在main函数调用backtracking前，先把迷宫起点加入visited：

vector<vector<int> > visited;
vector<int> decisions = {0,0};
vector<int> cPos = {0, 0}; // 简化起点初始化
visited.push_back(cPos); // 将起点存入已访问列表
backtracking(b, decisions, cPos, visited);

2. 在回溯逻辑中维护路径记录 #

回溯算法的核心是记录路径-探索-回溯恢复，所以要在backtracking里添加路径的存入与弹出操作，同时补全「根据决策更新当前位置」的逻辑（原代码完全缺失这一步，导致永远停在起点）：

void backtracking(vector<vector<int> > board, vector<int> &decisions, vector<int> &cPos, vector<vector<int> > &visited)
{
    int M = board.size();
    int N = board[0].size();
    
    // 终止条件：到达迷宫出口
    if (cPos[0] == N - 1 && cPos[1] == M - 1)
    {
        cout << "\nYou found the exit :D" << endl;
        return;
    }
    
    // 记录当前位置到路径中
    visited.push_back(cPos);
    
    // 获取下一步决策
    int d = makeDecision(cPos, board, visited);
    decisions.push_back(d);
    
    // 根据决策移动到新位置（这里假设d代表方向：0上/1下/2左/3右，可自行调整）
    switch(d) {
        case 0: cPos[1]--; break;
        case 1: cPos[1]++; break;
        case 2: cPos[0]--; break;
        case 3: cPos[0]++; break;
    }
    
    // 递归探索下一个位置
    backtracking(board, decisions, cPos, visited);
    
    // 回溯：恢复当前位置与路径记录
    switch(d) {
        case 0: cPos[1]++; break;
        case 1: cPos[1]--; break;
        case 2: cPos[0]++; break;
        case 3: cPos[0]--; break;
    }
    decisions.pop_back();
    visited.pop_back();
}

3. 给makeDecision添加边界检查 #

为了避免后续再出现越界问题，在访问前一个位置前先检查visited的大小：

int makeDecision(vector<int> currPos, vector<vector<int> > board, vector<vector<int> > &visited){

    int M = board.size();
    int N = board[0].size();
    int currX = currPos[0];
    int currY = currPos[1];

    // 边界检查：只有当路径长度≥2时，才能获取前一个位置
    if (visited.size() < 2) {
        // 处理初始情况（比如直接返回向右/向下的初始方向，根据你的迷宫规则调整）
        return 1;
    }

    vector<int> prevPos = visited[visited.size()-2];
    int prevX = prevPos[0];
    int prevY = prevPos[1];
    
    // 后续决策逻辑继续...
}

额外提醒 #

原代码还有一个致命逻辑漏洞：没有根据决策结果更新当前位置cPos，导致递归时永远停在起点，根本无法探索迷宫的其他区域，这部分已经在上述backtracking的修改中补全。

内容的提问来源于stack exchange，提问作者Alex M.