使用回溯C++解决迷宫

Question

我有这个二维矩阵迷宫。 “@”表示开始，“#”表示结束。 0表示路径被封锁，1表示可以通过。程序需要解决迷宫并打印找到的路径中每个元素的坐标。

输入示例：
5 10
@ 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1
0 1 0 1 0 1 1 1 0 1
1 1 1 1 0 1 0 0 0 1
# 0 0 1 1 1 1 1 1 1

第一行是矩阵的行和列。

#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){

    if(i == endX && j == endY){
        return;
    }

    cout << i << " " << j << endl;

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

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));


    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";
            }
        }
    }

    findPath(startX, startY, maze, visited, endX, endY, row, col);
}

我编写了这段代码，但它以分段错误结束并且没有输出。 它打印第一行的坐标，但当它必须向下时，它就会中断。

我的输出：
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9

我的方法是否错误，或者我错过了什么，请帮忙。

Answer 1

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

j + 1 < maxCol

是正确的检查，但为时已晚。

maze[i][j + 1]

和

visited[i][j + 1]

已被访问。您需要在访问数组之前而不是之后进行边界检查。与所有其他

if

陈述相同。

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