### Backtracking | Rat in a maze (Easy)

BACKTRACKING-RAT IN A MAZE
PROBLEM STATEMENT

A rat is standing in the starting block mat[0][0] of a maze, a N*N matrix named as mat[N-1][N-1]. It has  to reach to the end of the matrix, mat[N-1][N-1]. In the maze matrix, 0 means the block is a dead end and 1 means the block can be used in the path from source to destination.  It can move in the following directions.

• UP
• DOWN
• LEFT
• RIGHT

DIAGRAM

# ALGORITHM

1. Pass the matrix to shortestPath function, and create a visited matrix marking all the nodes as fase,i.e. unvisited
2. Calling the backtrack matrix with all parameters
3. Check if the node is valid, i.e. is not visited before and is satisfies the boundary conditions for the matrix
4. If the position is reached return 0
5. marked the node as visited so that in the next step, if the node comes in path it will not create an infinite loop to the same node.
6. Traverse to the left, right, up , and down cell of the matrix
7. Mark the node as unvisited, in case the same node comes in the another path, it may not be declared as invalid.
8. COMPLETED

# CODE

OUTPUT:
`The shortest path in the maze has: 8 nodes`