Rat Chases its cheese

#1

TEST CASE1,2 ARE FAILING HERE IS THE LINK

#2

@ayush1213
These are two seperate problems - “Rat in a maze” and “Rat chases its cheese” . The rat can only move right and down in the first one while it can move in all 4 directions in the second one. You are trying the code for the first problem in the second question. Hence there is no condition to move up or left for the rat. Make the according changes.

1 Like
#3

@tarunluthra sir i did the chance but now it is giving no output

#4

@ayush1213
Share the updated code please. Make sure to cover the base cases for the same as well. If you are simply using your old code , it won’t work as you need to update the base cases. The rat can go out of the grid in all 4 directions now. Also we do not want the rat to revisit the same visited cells again. Make sure to deploy these checks. If it still doesn’t work , share your new code here.

#5

@tarunluthra


sir it is the updated code

#6

@ayush1213
You are still missing one important base case. Since the movement is allowed in all 4 directions now , our code can go in an infinite recursion. Consider any point in our grid. Say we make a call to go right of that cell. We go right. Now at this cell we make a call to go left. We back to the original cell. Then again we repeat. As there is no condition to prevenr this , our rat can move left and right over just two cells infinitely. We need to deploy another base condition check to prevent this situation. Use your “out” array for this. We are already marking our visited cells in this array. If we visit an already visited cell , simply backtrack.

#7

@tarunluthra sir i got what u said but i m unable to backtrack

#8

@ayush1213
if( out[i][j] == 1)
return false;

#9

@tarunluthra SIR I DID THAT BUT STILL IT IS GIVING WRONG ANSWER HERE IS THE LINK:—

#10

@ayush1213
Remove the if condition
if(out[i][j]!=1)
after the downpath check.

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.