在二维迷宫中寻找路径

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 感谢大家的帮助。我已经纠正了我的错误。 这是更新后的ideone链接：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;
}

- nitte93

---

让它打印出它所访问的位置，你就会看到问题所在。 - interjay

Answer 1

这个问题是由于栈溢出引起的。你的深度优先搜索没有标记它所访问的位置，因此同一位置会被多次访问。

• 你从 (3, 2) 开始，尝试向左走。
• 这将带你到 (3, 1)。
• (3, 1) 左边没有路径，所以你向右走。
• 这将带你回到 (3, 2)，然后你再次尝试向左走。
• 这将带你到 (3, 1)。
• (3, 1) 左边没有路径，所以你又向右走……

看到问题了吗？要解决这个问题，请添加另一个数组来存储已经访问过的位置，并在继续搜索之前检查它。这将修复该问题。

- Sergey Kalinichenko

Answer 2

我猜代码导致无限递归调用。 你开始执行findPath(a,3,2)。 由于a[3][2]==1，代码将调用findPath(a,3,1)。 现在，由于a[3][1]==1，代码将再次调用findPath(a,3,2)... 以此类推...直到内存/堆栈溢出为止...

- Noamiko