2. Rat And Maze problem #

Created Thursday 25 June 2020

A rat has to travel between the top-left and the bottom right in a square grid. The maze has two types of places, normal floor(1) and holes(0). Find and print the number of ways it can do this, given the following contraints:

1. Holes are to be avoided.
2. Direction of movement from a cell can only be Left, Right, Up, Down.
3. We cannot pass through the walls.

• This is typical backtracking problem.
• Recursion will help us maintain current state.

Code:

• We need to keep a path matrix - We use this for printing the way.
• It is also used to keep track of the path.
• We place 0 for the unvisited places and 1 for the visited places.
• This path matrix is different from the **maze **matrix.`