Finding path in a 2-d maze

Question

Why is this code giving run-time error. I am trying to find if their exist a path inside the maze to reach the food(2). 0 representing obstacle, 1 representing path, and 2 is for the destination.

        `{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}`

I'm passing the starting point as findpath(a,3,2) where a is the maze and i=3, j=2 as the starting point. Code on ideone: http://ideone.com/poF9um

Thanks guys, for helping me. I have rectified my mistake. Here's the ideone link for the updated code: http://ideone.com/poF9um Thanks.

#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

The problem is caused by stack overflow. Your depth-first search does not mark locations that it visits, so the same location would be visited multiple times.

• You start at (3, 2), and try going left.
• This takes you to (3, 1).
• There is no path left of (3, 1), so you go right.
• This takes you back to (3, 2), from where you try to go left.
• This takes you to (3, 1).
• There is no path left of (3, 1), so you go right...

See the problem? To fix it, add another array of the spots that you have visited, and check it before continuing with the search. This will fix the issue.

Answer 2

I guess that the code causes infinite recursive calls. You begin with executing findPath(a,3,2). Since a[3][2]==1, the code will call findPath(a,3,1). Now, since a[3][1]==1, the code will later call again to findPath(a,3,2) again... And so on... Until you run out of memory / stack overflow...