3D迷宫递归方法 - C++

Question

我在C使3D迷宫++。我在递归方法中找到两个端点（起点为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; 

}

所以对于方法检查“出界”，路径（零），拜访位置上的无效点。我不确定我错过了什么，但是这个方法返回到不可解的迷宫。有人可以看到我的递归调用可能会遗漏一些明显的错误吗？由于

编辑：修正了一些代码错误，但它似乎仍然是“解决”无法解决的迷宫。

下面是跟它可解迷宫的例子是不可能解决：

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 

Answer 1

有一个在findPath(++row,column,level,path)（以及类似的递归调用）一个问题：你不想要的变量增量继续进行其他递归调用。 （例如，findPath(row,++column,level,path)中的变量row会受到第一次递归调用的影响。）

改为使用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]）。

Answer 2

我刚完成这个算法作为一个类的赋值，我们只使用了一个5x5块作为迷宫，但是我发现每次从任何角度到达块时，它都会非常缓慢地测试所有可能性，我发现通过将数组中的值设置为0，可以显着提高程序的速度，因为您确定它们无用。我在函数结尾的return false处做过。