追踪迷宫，从源头到达目标

我想实现一个问题的解决方案，其中我需要从源到目标递归地在迷宫中找到路径。追踪迷宫，从源头到达目标

假设这是迷宫： S X X X X X . . . . . X X . X X X X X . X X X X . . . X . G X X . . . X 其中

X-受阻路径

.-开放路径

S-开始

ģ-Goal

我有写下面的代码来实现解决方案，但它给我一个分段错误。如果有人能建议我我做错了，我会很高兴。

我的解决办法是

#include<iostream> 
using namespace std; 
void printGrid(char grid[6][6]) 
{ 
    for(int i=0;i<6;i++) 
    { 
     for(int j=0;j<6;j++) 
     { 
      cout<<grid[i][j]<<" "; 
     } 
     cout<<"\n"; 
    } 
} 

bool isValidPoint(char grid[6][6],int x,int y) 
{ 
    if(x<0 || x>5 || y<0 || y>5) 
    { 
     return false; 
    } 
    if(grid[x][y]=='X') 
    { 
     return false; 
    } 
    return true; 
} 

bool traceMaze(char grid[6][6],int x,int y) 
{ 
    if(!isValidPoint(grid,x,y)) 
    { 
     return false; 
    } 
    if(grid[x][y]=='G') 
    { 
     return true; 
    } 

    grid[x][y] = '+'; 

    if(traceMaze(grid,x-1,y)){return true;} 
    if(traceMaze(grid,x,y+1)){return true;} 
    if(traceMaze(grid,x+1,y)){return true;} 
    if(traceMaze(grid,x,y-1)){return true;} 

    grid[x][y] = '.'; 

    return false; 

} 


int main() 
{ 
    char grid[6][6] = {{'S','X','X','X','X','X'},{'.','.','.','.','.','X'},{'X','.','X','X','X','X'},{'X','.','X','X','X','X'},{'.','.','.','X','.','G'},{'X','X','.','.','.','X'}}; 
    cout<<"Initial grid is as follows :\n"; 
    printGrid(grid); 
    cout<<"\nStarting at : (0,0)\nTracing the path to the Goal\n"; 
    cout<<traceMaze(grid,0,0)<<"\n"; 
    cout<<"\nFinal grid is as follows :\n"; 
    printGrid(grid); 
    return 0; 
}

PS：我假设迷宫是6X6的大小...

Correct Solution :

我没有过任何检查的 '+'，我正在通过查看最后的追踪路径。

所以，现在我已经有应用了检查和isValidPoint功能转变为：

bool isValidPoint(char grid[6][6],int x,int y) 
{ 
    if(x<0 || x>5 || y<0 || y>5) 
    { 
     return false; 
    } 
    if(grid[x][y]=='X' || grid[x][y]=='+') 
    { 
     return false; 
    } 
    return true; 
}

感谢您的帮助球员:)

去年我得到了这个问题一个全职的采访。

来源

2014-10-02 Sameer Sawla

我在这里添加'+'的目的是看到跟踪的路径，它会在返回0之前反映在printGrid（）调用中; – 2014-10-02 04:22:27

调试器和几分钟的时间会几乎立即暴露您的错误。同样，在**之前立即使用'x'和'y'值的'std :: cerr'转储，并使用它们来取消您的迷宫阅读/写作。 – WhozCraig 2014-10-02 04:27:21

没有什么可以阻止你的traceMaze函数无限递归。即它将从一个网格点到下一个然后回到原始点。

最简单的修复方法是不处理并指向一个“+”作为进入的有效点（因为您已经在此路径中）。

来源

2014-10-02 04:31:02

Naah没有得到你的观点 – 2014-10-02 04:33:56

我有在isValidPoint＆如果检查与价值=='G'的基础案例这是不够的？ – 2014-10-02 04:34:53

哦，我知道了，我是否应该为'+'进行检查，还是应该用'X'替换它？ – 2014-10-02 04:37:36

黑暗的回答在我看来是有效的。

您的搜索从0,0开始。然后进入0,1，从那里回到0,0，再次回到0,1 ...你应该标记你已经去过的方块，而不是再去那里。 '+'很好，但是一旦你设置了它，你就不应该清除它，你应该在isValidPoint中检查它。

来源

2014-10-02 04:40:57 JoriO

是的。它确实有效。 – 2014-10-02 04:43:13

你正在做的是深度优先遍历迷宫。您正在使用+更改.以跟踪访问点，但完成后您将再次将它们更改为.。这就是问题。

假设A和B是迷宫的相邻细胞。在遍历A时，将A更改为+并递归遍历其邻居（包括B），然后再将A更改为.。然后，当您遍历B时，A是.，所以您再次从B开始遍历A，这不是必需的。

这就是为什么递归永远不会结束，并且您会遇到分段错误。

解决此问题的一种方法是保留一个单独的6x6阵列以跟踪访问点。当你完成一个单元格时（即遍历该单元格的所有可能的路径），将其标记为“已访问”的单元格，并且再也不访问已访问的单元格。

来源

2014-10-02 04:43:52 0605002

这是一个选项，但它会增加解决方案的空间复杂性。 – 2014-10-02 04:47:36

我在一张纸上写下了你的迷宫，并手工尝试了算法，并陷入了x = 2，y = 1的地方，你的算法想返回到x = 1，y = 1，返回到之前的状态。这种状态当然会进入上述状态，并创建一个无限循环。递归编程的一个重要规则是始终确保所有函数调用的所有执行路径都以回调（或类似的方式）结束。

如果您想获得有关主题的ballsy，我建议您查看shortest path problem解决方案使用例如Dijkstra's algorithm。

来源

2014-10-02 04:46:07 Tubbles

追踪迷宫，从源头到达目标

回答

相关问题