回溯法求解迷宫C++代码出现段错误问题求助

核心错误：数组越界访问 #

你的代码中所有方向判断的边界检查顺序错误，导致在访问数组元素之后才判断是否越界，直接触发段错误。例如：

if(maze[i][j + 1] == "1" && visited[i][j + 1] != "1" && j + 1 < maxCol)

当j处于最后一列（如示例中的j=9，maxCol=10），j+1=10已超出数组有效索引范围（列索引为0~9），但代码先访问了maze[i][j+1]，这会直接访问非法内存，导致程序崩溃。

修复步骤 #

1. 调整边界检查顺序 #

所有方向判断必须先检查边界合法性，再访问数组元素，修正后的四个方向判断如下：

// 向右
if(j + 1 < maxCol && maze[i][j + 1] == "1" && visited[i][j + 1] != "1"){
    findPath(i, j + 1, maze, visited, endX, endY, maxRow, maxCol);
}
// 向下
if(i + 1 < maxRow && maze[i + 1][j] == "1" && visited[i + 1][j] != "1"){
    findPath(i + 1, j, maze, visited, endX, endY, maxRow, maxCol);
}
// 向左
if(j - 1 >= 0 && maze[i][j - 1] == "1" && visited[i][j - 1] != "1"){
    findPath(i, j - 1, maze, visited, endX, endY, maxRow, maxCol);
}
// 向上
if(i - 1 >= 0 && maze[i - 1][j] == "1" && visited[i][j - 1] != "1"){
    findPath(i - 1, j, maze, visited, endX, endY, maxRow, maxCol);
}

2. 初始化visited数组 #

visited数组默认是空字符串，虽逻辑上可判断，但显式初始化为"0"更安全，避免未知行为。在main函数中添加：

// 初始化visited数组为"0"
for(int i = 0; i < row; i++){
    for(int j = 0; j < col; j++){
        visited[i][j] = "0";
    }
}

3. 补充终点坐标输出 #

当前代码到达终点时直接return，未输出终点坐标，导致路径不完整。修改终点判断逻辑：

if(i == endX && j == endY){
    cout << i << " " << j << endl; // 输出终点坐标
    return;
}

4. 优化路径输出（可选） #

当前代码进入函数就输出坐标，回溯时会重复输出无效路径点。改用路径栈记录当前路径，到达终点时再打印完整有效路径：

// 修改findPath函数，增加路径参数
void findPath(int i, int j, vector<vector<string>> &maze, vector<vector<string>> &visited, int endX, int endY, int maxRow, int maxCol, vector<pair<int, int>>& path){
    if(i == endX && j == endY){
        path.emplace_back(i, j);
        // 打印完整路径
        for(auto& p : path){
            cout << p.first << " " << p.second << endl;
        }
        path.pop_back();
        return;
    }
    if(visited[i][j] == "1") return; // 已访问过，直接返回

    visited[i][j] = "1";
    path.emplace_back(i, j);

    // 四个方向判断（已调整边界顺序）
    if(j + 1 < maxCol && maze[i][j + 1] == "1" && visited[i][j + 1] != "1"){
        findPath(i, j + 1, maze, visited, endX, endY, maxRow, maxCol, path);
    }
    if(i + 1 < maxRow && maze[i + 1][j] == "1" && visited[i + 1][j] != "1"){
        findPath(i + 1, j, maze, visited, endX, endY, maxRow, maxCol, path);
    }
    if(j - 1 >= 0 && maze[i][j - 1] == "1" && visited[i][j - 1] != "1"){
        findPath(i, j - 1, maze, visited, endX, endY, maxRow, maxCol, path);
    }
    if(i - 1 >= 0 && maze[i - 1][j] == "1" && visited[i][j - 1] != "1"){
        findPath(i - 1, j, maze, visited, endX, endY, maxRow, maxCol, path);
    }

    visited[i][j] = "0";
    path.pop_back();
}

// main函数中调用时新增路径容器
vector<pair<int, int>> path;
findPath(startX, startY, maze, visited, endX, endY, row, col, path);

修复后的完整代码 #

#include<bits/stdc++.h>
using namespace std;

void findPath(int i, int j, vector<vector<string>> &maze, vector<vector<string>> &visited, int endX, int endY, int maxRow, int maxCol, vector<pair<int, int>>& path){
    if(i == endX && j == endY){
        path.emplace_back(i, j);
        for(auto& p : path){
            cout << p.first << " " << p.second << endl;
        }
        path.pop_back();
        return;
    }
    if(visited[i][j] == "1") return;

    visited[i][j] = "1";
    path.emplace_back(i, j);

    if(j + 1 < maxCol && maze[i][j + 1] == "1" && visited[i][j + 1] != "1"){
        findPath(i, j + 1, maze, visited, endX, endY, maxRow, maxCol, path);
    }
    if(i + 1 < maxRow && maze[i + 1][j] == "1" && visited[i + 1][j] != "1"){
        findPath(i + 1, j, maze, visited, endX, endY, maxRow, maxCol, path);
    }
    if(j - 1 >= 0 && maze[i][j - 1] == "1" && visited[i][j - 1] != "1"){
        findPath(i, j - 1, maze, visited, endX, endY, maxRow, maxCol, path);
    }
    if(i - 1 >= 0 && maze[i - 1][j] == "1" && visited[i - 1][j] != "1"){
        findPath(i - 1, j, maze, visited, endX, endY, maxRow, maxCol, path);
    }

    visited[i][j] = "0";
    path.pop_back();
}

int main()
{
    freopen("input.txt", "r", stdin);

    int row, col;
    cin >> row >> col;
    
    vector<vector<string>> maze(row, vector<string>(col));
    vector<vector<string>> visited(row, vector<string>(col));

    // 初始化visited数组
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            visited[i][j] = "0";
        }
    }

    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            cin >> maze[i][j];
        }
    }

    int startX, startY, endX, endY;
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            if(maze[i][j] == "@"){
                startX = i;
                startY = j;
                maze[i][j] = "1";
            }
            if(maze[i][j] == "#"){
                endX = i;
                endY = j;
                maze[i][j] = "1";
            }
        }
    }

    vector<pair<int, int>> path;
    findPath(startX, startY, maze, visited, endX, endY, row, col, path);
}

内容的提问来源于stack exchange，提问作者chaos