首页 文章

3d迷宫递归方法 - c

提问于
浏览 次
1

我正在制作一个3D迷宫 . 我在使用递归方法找到两个 endpoints 之间的有效路径时遇到问题（起始点是m [0] [0] [0]; endpoints 是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++ algorithm methods recursion maze

2 回答

  • 0

    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] . ）

    回复于
  • 3

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

    回复于

相关问题