迷宫求解程序的回溯逻辑错误

Question

我写了一个简单的递归迷宫解决问题，它使用递归找到要解决的最少步数。但是，在死胡同中，程序无法备份跟踪的路径。

为了解决这个问题，我开始写移动函数的反函数。它们可用于反转路径，但仍需要一些方法来确定使用哪一个。

迷宫测试文件：

SWWWW
OOOOE
OWOWW
OOOWW

代码体：

//Read in maze
ifstream mazeFile;
mazeFile.open("MazeSample.txt");

vector<string> mazeRead{ istream_iterator<string>(mazeFile), istream_iterator<string>() };
maze = mazeRead;


    //Move checks
vector<string> maze;
int numMoves;
int leastMoves = 1000;

int row;
int column;

bool canMoveUp(int row, int column) {
    try {
        if (maze.at(row - 1).at(column) != ('O')) {
            cout << "(Can't move up)" << endl;
            if (maze.at(row - 1).at(column) == 'E') {
                return true;
            }
            return false;
        }
    }
    catch (const out_of_range& error) {
        cout << "(Can't move up)" << endl;
        return false;
    }
    return true;
}

bool canMoveDown(int row, int column) {
    try {
        if (maze.at(row + 1).at(column) != ('O')) {
            cout << "(Can't move down)" << endl;
            if (maze.at(row + 1).at(column) == 'E') {
                return true;
            }
            return false;
        }
    }
    catch (const out_of_range& error) {
        cout << "(Can't move down)" << endl;
        return false;
    }
    return true;
}

bool canMoveLeft(int row, int column) {
    try {
        if (maze.at(row).at(column - 1) != ('O')) {
            cout << "(Can't move left)" << endl;
            if (maze.at(row).at(column - 1) == 'E') {
                return true;
            }
            return false;
        }
    }
    catch (const out_of_range& error) {
        cout << "(Can't move left)" << endl;
        return false;
    }
    return true;
}

bool canMoveRight(int row, int column) {
    try {
        if (maze.at(row).at(column + 1) != ('O')) {
            cout << "(Can't move right)" << endl;
            if (maze.at(row).at(column + 1) == 'E') {
                return true;
            }
            return false;
        }
    }
    catch (const out_of_range& error) {
        cout << "(Can't move right)" << endl;
    }
    return true;
}


    //Maze solve function
void solve(int row, int column) {
    numMoves = numMoves + 1; //count moves

    //Base case (solution found; current position is 'E')
    if (maze[row][column] == 'E') {
        if (numMoves < leastMoves) {
            leastMoves = numMoves;
        }
    }

    if (maze[row][column] != 'E') {
        maze[row][column] = 't'; //mark path
    }

    // move up and see if move leads to solution (recursively)
    if (canMoveUp(row, column)) {
        cout << "(Move up)" << endl;
        row = row - 1;
        column = column;
        solve(row, column);
    }

    // if move chosen above doesn't lead to solution, move down & check
    if (canMoveDown(row, column)) {
        cout << "(Move down)" << endl;
        row = row + 1;
        column = column;
        solve(row, column);
    }

    // if move chosen above doesn't lead to solution, move left & check
    if (canMoveLeft(row, column)) {
        cout << "(Move left)" << endl;
        row = row;
        column = column - 1;
        solve(row, column);
    }

    // if move chosen above doesn't lead to solution, move right & check
    if (canMoveRight(row, column)) {
        cout << "(Move right)" << endl;
        row = row;
        column = column + 1;
        solve(row, column);
    }

    // if no above solution works, then unmark cell
    //backtrack (keeps going until all solutions reached)
    maze[row][column] = 'O';
    cout << "Mark as 'O'";
    numMoves = numMoves - 1;


    //TODO: PROBLEM: ROW/COLUMN NOT RESET AFTER STUCK; KEEPS SAME VALUE
            //Questionable code
    if (!canMoveUp(row, column)) {
        //Inverse of canMove?
        row = row + 1;
        column = column;
    }


    //Display vector contents
    cout << endl;
    for (int row = 0; row < maze.size(); row++) {
        cout << endl;
        for (int column = 0; column < maze[row].size(); column++) {
            cout << maze[row][column];
        }
    }
    cout << endl;
}

当遇到死胡同时，我希望迷宫能回到最后一个有移动选项的路口。相反，光标来回移动，无法解决。这可能是由于移动功能的实现；如果能够移动，它将 row/column 变量设置为新的 space.

错误路径如下所示，在第 1 行第 1 列的 't' 和 'O' 之间切换：

SWWWW
tttOE
tWtWW
tttWW

SWWWW
tOtOE
tWtWW
tttWW

在无法向四个方向中的任何一个方向移动时，我希望代码能够撤消之前的移动，直到到达最后一个路口。

Answer 1

无需深入研究您的算法

if (canMoveUp(row, column)) {
    cout << "(Move up)" << endl;
    row = row - 1;
    column = column;
    solve(row, column);
}

看起来很可疑。您正在更改您在后续块中使用的变量 row 和 column。如果 canMoveUp 为真，下一次检查将是 canMoveDown('originalrow' - 1, column)，这将失败（因为它再次向该行添加 1 并检查您刚刚用 t.

标记的字段

不应该吗

if (canMoveUp(row, column)) {
    cout << "(Move up)" << endl;
    solve(row - 1, column);
}

迷宫求解程序的回溯逻辑错误

Backtracking logic error with maze solving program

c++

recursion

c++11

2d-vector