RAT IN A MAZE PROBLEM

#1

Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are ‘U’(up), ‘D’(down), ‘L’ (left), ‘R’ (right). Value 0 at a cell in the matrix represents that it is blocked and rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it.
Note: In a path, no cell can be visited more than one time.

ATTEMPT LINK:https://ide.geeksforgeeks.org/dBWq9968ns

Please help me understand how the code is wrong.

#2

hi @amartyaprabhakar
If destination is reached print the solution matrix .
Else .
a) Mark current cell in solution matrix as 1.
b) Move forward in the horizontal direction and recursively check if this move leads to a solution.
c) If the move chosen in the above step doesn’t lead to a solution then move down and check if this move leads to a solution.
d) If none of the above solutions works then unmark this cell as 0 (BACKTRACK) and return false

refer this code -->

Hope it clears ur doubt…

#3

hi @amartyaprabhakar
is it clear now??

#4

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.

#5

Yes sir clear now.
Thank you for your help.

1 Like