Ошибка логики возврата с программой решения лабиринта - PullRequest
Новая
       23

Ошибка логики возврата с программой решения лабиринта

0 голосов
/ 08 июля 2019

Я написал простую рекурсивную задачу решения лабиринта, которая использует рекурсию, чтобы найти наименьшее количество ходов для решения.Однако в тупиках у программы возникают проблемы с резервным копированием трассированного пути.

Чтобы попытаться решить проблему, я начал писать обратные функции функций перемещения.Их можно использовать для обратного пути, но все равно потребуется какой-то способ определить, какой из них использовать.

Тестовый файл лабиринта: 

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

Когда я зашел в тупик, я ожидал, что лабиринт вернется к последнему перекрестку с вариантами движения.Вместо этого курсор перемещается назад и вперед, не решая проблему.Это, вероятно, связано с реализацией функций перемещения;если он может двигаться, он устанавливает переменные строки / столбца в новое пространство.

Путь ошибки выглядит следующим образом, переключаясь между 't' и 'O' в строке 1, столбец 1: 

SWWWW
tttOE
tWtWW
tttWW

SWWWW
tOtOE
tWtWW
tttWW

Будучи не в состоянии двигаться ни в одном из четырех направлений, я ожидал, что код отменит предыдущее (ые) движение (я) до достижения последнего перекрестка.

1 Ответ

2 голосов
/ 08 июля 2019

Не заглядывая слишком глубоко в ваш алгоритм 

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