Backtracking in RAT MAZE

general
, , ,
1

Hello everyone,
I have a problem in backtracking the solution in RAT maze . The problem
just needs the number of solutions to the maze. But i wanted to determine what are the solutions of this maze.

Like we must find all the path in which the rat must move to reach destination,
i.e.,directions need to be followed…l-left, r-right, d-down, u-up.

One solution of the following example is rrdd denoting right right down down.

Input

3

0 0 0

0 1 0

0 0 0

Output

2

rrdd

ddrr

2

I can only give you algorithm but it is very easy to convert it to code :slight_smile:

I hope you know how to calculate the number of ways for your example the numbers of ways is 2 it can be calculate easily using another matrix ( Let us denote WM) to store number of way to reach aparticular block so

for

0 0 0

0 1 0

0 0 0
WM will be

1 1 1

1 0 1

1 1 2

( if you have doubt in how i calculated above WM , Comment… I will explain )

Now you have WM and it is known that we MUST start from upper leftmost block
in order to generate all the ways
u can use following pseudo code ( it uses stack )…

def print_path(present block , stack , direction)
 if present block has zero :
      return
 if present block is destination:
      print all the entries in stack and the direction also
 else
   decrease one in present block
   push the direction in stack
   print_path(present block to right , stack , right);
   print_path(present block to down , stack , down);
 return;

after writing the algo i came to know that we can go up and left also :frowning: I Only did for right down may be you can extend this to that also :slight_smile: , you take care of the limiting conditions like end of matrix etc…

3

@usaxena95: this can be solved using recursion.

think that u are in position (x,y),after that see

  1. if (x-1,y) is possible to go, if yes add letter u to the dir string and call the function again with (x-1,y) as (x,y).

  2. similarly check for (x+1,y),(x,y+1),(x,y-1), u have to make sure that visited cells are not visited again.

  3. whenever ur x and y equals n-1 print the dir string.

  4. (to calculate the number of paths there is no need to calculate dir just increment a variable say numpaths when ever x and y equals n-1)

just added the link to java solution incase u wanted to refer :).

1 Like