# MAZE problem

Hey there,
So I was solving this problem
http://www.codechef.com/CODW2012/problems/BPHC03
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,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

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

Can this also be done using BFS?

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.

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.

Try different inputs with this code and look at how “maze” reacts:
http://ideone.com/MZ7Vjd

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

1 Like