1

我正在用 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
4

2 回答 2

4

（和类似的递归调用）存在一个问题findPath(++row,column,level,path)：您不希望变量增量延续到其他递归调用。（例如，变量rowinfindPath(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]什至会在第一次调用这个函数之前检查一下。）

于 2012-12-07T02:24:51.203 回答
0

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

于 2013-11-01T05:49:59.130 回答