MAZE problem

general
, , ,
1

Hey there,
So I was solving this problem


I know how to check whether a path exists from 1,1 to n,n
My logic uses recursion by making the entry as 1 in maze to block the path from where it just came 
void calc(int maze[100][100],int n,int i,int j)  
{
     
     if(i<0 || i>=n || j<0 || j>=n)
     return;
     if(maze[i][j]==1)
     return;
     if(i==n-1 && j==n-1)
     {
               count++;
               return;
     }
     maze[i][j]=1;
     
     calc(maze,n,i+1,j);
     calc(maze,n,i-1,j);
     calc(maze,n,i,j+1);
     calc(maze,n,i,j-1);
     
     return;
}

This snippet does not produce the exact answer…infact it shows less number of paths as after calculation of each path many entries are made 1 (or blocked) which hinders exploration of paths which might use a part of the previously explored path and some other new path…
I hope you got my point.
Please tell me how I calculate the number of paths.
Thanx

2

Try to follow the execution steps by steps for this input:

3
0 0 1
0 0 1
0 0 0

Your code will give output “1” I think. But the answer must be “4”.

1 Like
3

Yes exactly… So i need to know how to overcome this shortcoming.
I know my code will give an answer less than the expected value because at the end of 1 exploration many vertices in the maze would be turned to 1 thus hindering the next exploration. Please give me a solution to this.

4

I can’t give you the answer directly, it will be a little easy…
Try to print the different variables you use on your code at different time. Your 2D array “maze” contains bad informations sometimes.

5

Try different inputs with this code and look at how “maze” reacts:

6

Yah got it… maze[i][j]=0 should be added after the 4 recursive calls :slight_smile: :slight_smile: Thanks

1 Like
7

Can this also be done using BFS?