Rat in the maze in C++

By Priyanshu Prakash

Rat in the maze is a technique to clear the concept of backtracking. It is used to find the shortest path to arrive at the original destination.

language used:- C++

In the given problem there is a given maze N*N. Some cells are valid to move and some cells are blocked. If one rat starts moving from the start vertex to the destination vertex, we have to find that is there any way to complete the path, if it is possible then mark the correct path for the rat.

Algorithm used:-Backtracking 

Create a Solmatrix. Create a recursive function that takes the 1st matrix, output matrix, and position of sol(i, j). If the position is not matched or blocked come back the original position.Mark the position output[i][j] as one and check. If the destination is successfully arrived print the output matrix and come back. Recursively demand position (i+1, j) and (i, j+1). Unused position (i, j), i.e ans[i][j] = zero.