c++ - 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;

所以该方法检查“越界”，路径上的无效点(零)，访问位置。我不确定我到底遗漏了什么，但该方法对无法解决的迷宫返回 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 

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;

编辑

但是，您实际上并不需要这些测试，因为您在递归函数的顶部过滤掉了越界 错误。因此，这些调用可以简化为:

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]。)