在二维迷宫中寻找路径

Question

为什么此代码给出运行次错误。我试图找到他们是否存在迷宫内到达食物的路径（2）。 0代表障碍，1代表路径，2代表目的地

        `{0,1,1,0,0},
         {1,0,1,1,1},
         {0,0,0,0,0},
         {0,1,1,1,1},
         {0,0,1,1,0},
         {1,0,1,1,2}`

我将起点设为 findpath(a,3,2)，其中 a 为迷宫，i=3、j=2 为起点。 ideone 上的代码：http://ideone.com/poF9um

谢谢大家帮助我。我已经纠正了我的错误。这是更新代码的创意 link：http://ideone.com/poF9um 谢谢。

#include <iostream>
using namespace std;

/*int insideMaze(int x, int y){
if(x>=6 || y >=5 || x<0 || y< 0)
{
    return 0;
}
return 1;
}*/
bool findPath(int a[6][5], int n1, int m1){
if(n1>=6 || m1 >=5 || n1<0 || m1<0){
    return false;
}

if(a[n1][m1] == 0){
    return false;
}
if(a[n1][m1]==2){
    return true;
}
//a[n1][m1] = 4;
if(findPath(a,n1-1,m1)==true){
    return true;
}
if(findPath(a,n1,m1-1)==true){
    return true;
}
if(findPath(a,n1+1,m1)==true){
    return true;
}
if(findPath(a,n1,m1+1)==true){
    return true;
}

return false;
}

int main() {
// your code goes here
//int a[10][10];
int a[6][5] = {
         {0,1,1,0,0},
         {1,0,1,1,1},
         {0,0,0,0,0},
         {0,1,1,1,1},
         {0,0,1,1,0},
         {1,0,1,1,2}
        };
if(findPath(a,3,2)){
    cout<<"Path Found";
}

return 0;
}

Answer 1

问题是由堆栈溢出引起的。您的深度优先搜索不会标记它访问过的位置，因此会多次访问同一个位置。

您从 (3, 2) 开始，然后尝试向左走。
这会将您带到 (3, 1)。
(3, 1)左边没有路，你往右走。
这会将您带回 (3, 2)，从您尝试向左走的地方。
这会将您带到 (3, 1)。
(3, 1)左边没有路，所以你往右走...

看到问题了吗？要修复它，请添加另一个您访问过的地点的数组，并在继续搜索之前检查它。这将解决问题。

Answer 2

我猜测代码会导致无限递归调用。您从执行 findPath(a,3,2) 开始。由于 a[3][2]==1，代码将调用 findPath(a,3,1)。现在，由于 a[3][1]==1，代码稍后将再次调用 findPath(a,3,2) ... 依此类推...直到运行内存不足/堆栈溢出...

在二维迷宫中寻找路径

Finding path in a 2-d maze

c++

maze