# Rat in a maze problem using backtracking | faceprep

Program to solve Rat in a maze problem using backtracking is discussed here. Given a maze where 1 represent free space and 0 represented it is blocked. Print the path from 0,0 to n-1,n-1 if exists or print -1;

Consider the maze given below.

Gray blocks represent dead ends (value = 0) and path can be traced only using the white path(value = 1).

The binary matrix representation of the above maze (a) is given as

```{1, 0, 0, 0}
{1, 0, 0, 0}
{1, 1, 1, 1}
{0, 0, 0, 1}```

The highlighted lines in (b) show the path to reach the destination from the source.

## Algorithm for rat in a maze problem

1. If the destination point is reached,

•      Print the solution_matrix.

2. Else

• Mark the current cell in the solution_matrix as 1.
• Move forward in the horizontal direction and recursively check if this move leads to the solution.
• If the move chosen in the above step doesn’t lead to a solution then move down and check if this move leads to the solution.
• If none of the above solutions works then unmark this cell as 0 (backtrack) and return false.

Program for rat in a maze problem is given below.

/* C++ program for rat in a maze problem */
#include<iostream>
using namespace std;
bool isSafe(int r,int c,int n,int **maze)
{
if( r < 0 || r >= n )
return false;
if( c < 0 || c >= n )
return false;
if(maze[r][c])
return true;
return false;
}
bool solvemaze(int ** maze,int i,int j,int ** soln,int n)
{
if(i == n-1 && j == n-1)
{
soln[i][j]=1;
return true;
}
if(isSafe(i,j,n,maze))
{
soln[i][j]=1;
if(solvemaze(maze,i+1,j,soln,n))
return true;
if(solvemaze(maze,i,j+1,soln,n))
return true;
soln[i][j]=0;
}
return false;
}
int main()
{
int n;
cin>>n;
int** maze = new int*[n];
for(int i = 0; i < n; ++i)
maze[i] = new int[n];
int** soln = new int*[n];
for(int i = 0; i < n; ++i)
soln[i] = new int[n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>maze[i][j];
soln[i][j]=0;
}
}
if(solvemaze(maze,0,0,soln,n))
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<soln[i][j]<<” “;
cout<<endl;
}
}
else
{

cout<<“-1”;
}
}

Test Case 1

I/P
3
1 1 0
0 1 1
1 1 1
O/P
1 1 0
0 1 0
0 1 1

Test Case 2

I/P
5
1 1 0 0 1
0 1 1 1 0
1 1 1 0 1
1 1 1 1 1
1 1 1 1 1
O/P
1 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 1 1 1

Test Case 3

I/P
5
1 0 0 0 1
0 1 1 1 0
1 1 1 0 1
1 1 1 1 1
1 1 1 1 1
O/P
-1

Test Case 4

I/P
4
0 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1
O/P
-1

Test Case 5

I/P
4
1 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1
O/P
1 0 0 0
1 0 0 0
1 1 1 1
0 0 0 1