Rat Chases its Cheese

#1

I am not able to figure out why 3 test cases are failing.

#2

hi,
you need to maintain visited cells as well. so that you don’t visit them again and thus reducing the time complexity.

the modified code is:
#include<bits/stdc++.h>
using namespace std;
int n,m,path[10][10]={0};
char maze[10][10];
bool visited[10][10];
bool cheese(int i,int j)
{
visited[i][j] = true;
if(i==n-1 && j==m-1)
{
path[i][j]=1;
return true;
}
if(i>n-1 || j>m-1 || maze[i][j]==‘X’) return false;
path[i][j]=1;
if(!visited[i][j+1] && cheese(i,j+1)) return true;
if(!visited[i+1][j] && cheese(i+1,j)) return true;
path[i][j]=0;
return false;
}
int main()
{
cin>>n>>m;
memset(maze,‘X’,sizeof(maze));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>maze[i][j];
if(cheese(0,0) && maze[0][0]!=‘X’ && maze[n-1][m-1]!=‘X’)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<path[i][j]<<" ";
cout<<endl;
}
}
else cout<<“NO PATH FOUND”;
return 0;
}

1 Like
#4

but my code is giving wrong answer… not time error
This is simply memoized form of the same code. the answer should not change.

#5

yes you are right, I just memoized the code. the actual problem is you ignored up and left movement. initially I also thought that there is no need of up and left movement but its not true.
think about the case
OOOOO
OOOOO
OXXXX
OXOOO
OOOXO

also add two more recursive calls (i,j-1) and (i-1,j). and you must memoize in this case, otherwise infinite recursion.
thanks

1 Like
#6

thank you… now i got it

#7

please rate and resolve it.
thanks