алгоритм — метод рекурсии 3d лабиринт

Question

алгоритм — метод рекурсии 3d лабиринт

Я делаю 3D лабиринт в C ++. У меня возникли проблемы с рекурсивным методом, чтобы найти правильный путь между двумя конечными точками (начальная точка 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

1

algorithm c++maze methods recursion

Решение

Другие решения

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

0

Источник

Accepted Answer

Есть проблема в 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] кстати, даже до первого вызова этой функции.)

3