Метод рекурсии трехмерного лабиринта - С++

Я делаю трехмерный лабиринт на С++. У меня возникли проблемы с рекурсивным методом поиска допустимого пути между двумя конечными точками (начальная точка — m[0][0][0]; конечная точка — m[7][7][7];). Он проверяет позиции в массиве. Если его содержимое равно 1, то это допустимая часть пути; если 0, это недопустимая часть пути. Вот мой метод:

bool Maze::findPath(int row, int column, int level,string path){
cout << "findPath " << row << ", " << column << ", " << level << " value " << m[row][column][level] << endl;
if(row < 0 || row > 7 || column < 0 || column > 7 || level < 0 || level > 7 ){
    cout << "Out of bounds" << endl;
    //system("PAUSE");
    return false;
}
else if(m[row][column][level] == 0){
    cout << "spot is zero" << endl;
    //system("PAUSE");
    return false;
}
else if(visited[row][column][level] == 1){
    cout << "visited" << endl;
    return false;
}
else if(row == 7 && column == 7 && level == 7 && m[row][column][level] == 1){
    cout << "Found!" << endl;
    //system("PAUSE");
    return true;
}
else{
    visited[row][column][level] = 1;
    //cout << "searching..." << endl;
    if(row < 7 && findPath(row + 1,column,level,path))
        return true;
    if(column < 7 && findPath(row,column + 1,level,path))
        return true;
    if(level < 7 && findPath(row,column,level + 1,path))
        return true;
    if(row > 7 && findPath(row - 1,column,level,path))
        return true;
    if(column > 7 && findPath(row,column - 1,level,path))
        return true;
    if(level > 7 && findPath(row,column,level - 1,path))
        return true;
}
return false;

}

Таким образом, метод проверяет «За пределами», недопустимое место на пути (ноль), посещаемое место. Я не уверен, что именно мне не хватает, но метод возвращает true для неразрешимых лабиринтов. Может ли кто-нибудь увидеть какую-то вопиющую ошибку, которую я могу пропустить с моим рекурсивным вызовом? Спасибо

РЕДАКТИРОВАТЬ: исправлено несколько ошибок кода, но он по-прежнему «решает» неразрешимые лабиринты.

Вот пример разрешимого лабиринта, который невозможно решить:

1 0 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 1 0 0 0 0 
1 0 0 1 0 1 0 0 
0 0 0 1 0 0 0 0 
1 0 0 1 0 0 0 1 

1 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 
1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 1 1 0 0 0 0 0 
0 0 0 1 0 1 1 1 

0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
1 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 

1 1 1 1 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 
1 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 
1 0 0 0 0 0 0 1 

1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 
1 1 1 1 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 0 
1 1 1 1 0 0 0 1 

1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 1 0 0 0 0 0 

0 0 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
0 0 1 1 0 0 0 1 
0 0 0 1 0 0 0 1 
0 0 0 1 0 0 0 1 
0 0 0 1 1 1 0 1

c++ methods recursion algorithm maze
person jordan    schedule 07.12.2012    source источник
comment
Подождите, это решение неразрешимых лабиринтов или не решение разрешимых? Или оба?   -  person irrelephant    schedule 07.12.2012
comment
Вот рабочая версия, если поможет :) ideone.com/mIW6eY   -  person Carl    schedule 07.12.2012

Ответы (2)


arrow_upward
3
arrow_downward

В findPath(++row,column,level,path) (и подобных рекурсивных вызовах) есть проблема: вы не хотите, чтобы приращения переменных переносились на другие рекурсивные вызовы. (Например, на переменную row в findPath(row,++column,level,path) повлияет первый рекурсивный вызов.)

Вместо этого используйте findPath(row + 1,column,level,path) (и подобные).

Кроме того, в последних трех рекурсивных вызовах вы делаете неправильные тесты:

//instead of level < 7
if(level < 7 && findPath(--row,column,level,path)) //should be row > 0
    return true;
if(level < 7 && findPath(row,--column,level,path)) //should be column > 0
    return true;
if(level < 7 && findPath(row,column,--level,path)) //should be level > 0
    return true;

РЕДАКТИРОВАТЬ

Однако на самом деле вам не нужны эти тесты, поскольку вы отфильтровываете out of bounds ошибок в верхней части вашей рекурсивной функции. Следовательно, эти вызовы можно упростить до:

return  findPath(row + 1,column,level,path) || findPath(row,column + 1,level,path)
          || findPath(row,column,level + 1,path) || findPath(row - 1,column,level,path)
          || findPath(row,column - 1,level,path) || findPath(row,column,level - 1,path);

Кроме того, тест && m[row][column][level] == 1 является избыточным, поскольку об этом позаботится else if(m[row][column][level] == 0). (Кстати, я бы проверил m[7][7][7] еще до вызова этой функции в первый раз.)

person irrelephant    schedule 07.12.2012
comment
Спасибо за ответ. Все еще с той же проблемой. Кроме того, внесение предложенных вами изменений приводит к сбою теста за пределами границ. Почему я не хочу, чтобы приращение переносилось? - person jordan; 07.12.2012
comment
Вы не хотите, чтобы приращение переносилось, потому что тогда вы не будете тестировать единичные шаги в каждом направлении; вы будете делать диагональные шаги, оставаться на месте или делать другие странные вещи. :) - person irrelephant; 07.12.2012
comment
Будьте здоровы! Я не заметил, что они все тестировали уровень. Большое спасибо! - person jordan; 07.12.2012
comment
Как только моя репутация станет достаточно высокой, я проголосую за этот ответ! Спасибо еще раз! - person jordan; 07.12.2012
comment
@user1732610 user1732610 Не за что :) Я почти уверен, что вы можете принять ответ (конечно, если вы чувствуете, что этот ответ решает проблему). - person irrelephant; 07.12.2012
comment
@ user1732610 Однако я не думаю, что эта ошибка проверки уровня слишком важна, поскольку вы фильтруете границы в верхней части рекурсивной функции. - person irrelephant; 07.12.2012
comment
Кажется, он все еще решает неразрешимые лабиринты. Я не уверен, как он попадает на другую конечную точку. Я не думаю, что он совершает диагональные прыжки. Я сейчас смотрю на это. - person jordan; 07.12.2012
comment
Не могли бы вы привести пример простого неразрешимого лабиринта, для которого программа неверна? - person irrelephant; 07.12.2012
comment
@user1732610 user1732610 Может ли быть ошибка при чтении данных? (распечатайте массив m, чтобы увидеть, соответствует ли он вашим ожиданиям) - person irrelephant; 07.12.2012
comment
Я не думаю, что есть какие-либо ошибки при чтении данных. Я сделал несколько cout-ов для проверки. Я включил пример лабиринта выше, который терпит неудачу. Я не уверен, насколько это будет полезно. Я смотрю прямо сейчас, чтобы увидеть, где в лабиринте он терпит неудачу. - person jordan; 07.12.2012
comment
Вы помогли мне тонны и направили меня в лучшем направлении. Я собираюсь проверить ваш ответ. Спасибо за огромную помощь. - person jordan; 07.12.2012
comment
@user1732610 user1732610 О, кажется, у вас все еще не было правильных тестов: row > 7, level > 7 и level > 7 должны быть row > 0 и т. д. Я бы просто удалил их все, как в моем редактировании. - person irrelephant; 07.12.2012
comment
Да, я пошел дальше и избавился от них. Спасибо! - person jordan; 07.12.2012

arrow_upward
0
arrow_downward

Я только что закончил этот алгоритм в качестве задания для класса, наш использовал только блок 5x5 в качестве лабиринта, но я обнаружил, что он будет очень медленно проверять все возможности каждый раз, когда он достигает блока под любым углом, я обнаружил, что программа может можно значительно ускорить, установив значения в вашем массиве на 0, поскольку вы определяете, что они бесполезны. Я сделал это в return false в конце функции.

person Eric    schedule 01.11.2013