Rat in a Maze Problem (Backtracking)

rat in a maze problem

Problem Statement

The problem is a rat in a maze problem. Consider a rat placed at (0, 0) in a square matrix of order N*N. It has to reach the destination at (n-1, n-1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line contains an integer N denoting the size of the square matrix. The next line contains N*N space-separated values of the matrix m where 0’s represents blocked paths and 1 represents valid paths.

Output:
For each test, case output will be space-separated sorted strings denoting all directions, which the rat could take to reach the destination. Print -1 if no such path exists.

User Task:
Your task is to complete the function printPath() which returns a sorted array of strings denoting all the possible paths which the rat can take to reach the destination at (n-1, n-1). If no such path exists the function should return an empty array.

Constraints:
1 <= T <= 100
2 <= N <= 5
0 <= matrix[i][j] <= 1


Example
Input:

3
4
1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1
4
1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1
2
1 0 1 0 

Output:
DRDDRR
DDRDRR DRDDRR
-1
Explanation:
Testcase 2: The given input is in the form
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
For the above matrix the rat can reach the destination at (3, 3) from (0, 0) by two paths ie DRDDRR and DDRDRR when printed in sorted order we get DDRDRR DRDDRR.

Analysis of Problem Statement

You are given 2-D matrix of size N*N and you have to find all paths so that rat can reach the maze. In N*N matrix ‘1’ signifies that you can move to that block and ‘0’ signifies that you cannot move to that block.

Rat is initially at (0,0) cell and maze is present at (N-1,N-1) cell. Now you have to find all paths if present for the rat to reach its maze.

rat in a maze problem
rat in a maze problem

In the above example, there is one path present. Your task is to print the direction in which rat should move to reach it’s destination. The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).

Output : DRRURRDDLDDR

If multiple paths are present you should print all the paths separated by a space.

Hope Problem Statement is clear.

Approach to the Rat in a maze problem

This is clearly a backtracking Problem, where we have to find the path from source to destination.

To solve this puzzle, we first start from the source and move in a direction where the path is not blocked. If taken path makes us reach to the destination then the puzzle is solved else, we come back and change our direction of the path taken.

Here we will write a recursive Algorithm which will search it’s path by it’s own, we just need to specify some of the conditions and rest work will be done by recursion itself.

Let’s move step by step so that we can understand the algorithm clearly.

Recursive Function

It’s clear that we will solve this problem by using recursion. So, let’s discuss the approach to write the recursive function.

Base Condition for the Recursion

The base condition will be simple, we cannot go out of the square matrix, and also we cannot move to the block with integer ‘0’ because ‘0’ means path is blocked.

Also, we will keep track of a visited array, to insure that we are not visiting the same block which we crossed earlier. So if the block is already visited, we will simply return it.

So, these are the base condition required for our algorithm.

Let see the code for base condition,

if(i < 0 || i >= n || j < 0 || j >= n)
{
    return;                // For not going out of the square matrix
}
if(m[i][j] == 0){
    return;                // For not going to the blocked area
}
if(vis[i][j] == 1){
    return;                // For not going to the visited block 
}

Hope above base condition is clear to you, these are very simple conditions. So, let’s move ahead.

Main body of the Recursion

For the sake of simplicity, let’s first find the path for the rat to reach the maze or let us first check whether there is any path present or not for the rat to reach the maze.

Later, we will modify the recursion to also find the direction of the path.

The body of the recursion will be simple, the rat can move only in four directions. So if the current position of the rat is M[x][y], then it can move to M[x-1][y], M[x+1][y], M[x][y-1], M[x][y+1]. Isn’t it?

It is as simple as that and this is the information we need to specify in the body of the recursion and rest work will be tackled by our base condition.

So, let’s see the code and we will then understand it by an example.

Code

int cnt = 0;
void dfs(int m[MAX][MAX],int i,int j,int n,int vis[MAX][MAX])
{
    if(i < 0 || i >= n || j < 0 || j >= n) return;                
    if(m[i][j] == 0 || vis[i][j] == 1) return;        
    
    if(i == n-1 && j == n-1)
    {
        cnt++;
        vis[i][j] = 0;
        return;
    }
    
    vis[i][j] = 1;
  
    dfs(m,i-1,j,n,vis);
    dfs(m,i+1,j,n,vis);
    dfs(m,i,j-1,n,vis);
    dfs(m,i,j+1,n,vis);
    
    vis[i][j] = 0;
    return; 
}

If we reach the coordinate M[n-1][n-1] then count will get updated from that we will know if there is any path present or not.

Let us understand the code step by step and also with an help of a example.

The parameters of the recursive function are simple, the matrix M[][], the coordinates [i][j], the size of the array N and the visited array for keeping the track of the path.

rat in a maze problem

This is the 2-D Matrix given to us and we are currently at the source M[0][0] and we have to reach the maze present at M[3][3].

Now let us analyse the recursion by the help of below diagram.

rat in a maze problem

Hope, the above diagram is clear. The recursion tree is incomplete but the process will go on like this.

Note the recursive call which are returning is actually going to our base condition.

dfs(-1, 0) is actually going out of the square matrix.
dfs(0, 0) is actually visited before, so it is returned.

By going this way, this Algorithm will find it’s own path. Hope the recursion body is clear to you. If not clear then try to draw a recursion diagram by taking a small example and try to follow the steps which I have mentioned above.

What if a path is found ??

Now suppose the above algorithm finds a path by the above recursion but this is not the end of our solution.

We need to find all the path from source to destination. So for this we will again return back and we will unvisit the visited block, so that it can find more ways to reach the destination.

We will try to understand this part by taking an small example,

rat in a maze problem

In the above example, there are two paths to reach destination. We will see it’s recursion tree to understand how we will find both the paths.

rat in a maze problem

The first path is found, now our task is to find the second path, for this we will unvisit the remaining nodes and we will try to find the other path.

rat in a maze problem

This is how, recursion will find the second path, first it will unvisit the visited node (marked by grey) and then recursion will continue. This way it will find the second path.

Hope recursion is clear and now I hope you can visualize the bigger picture that how rat is finding it’s own way to reach the maze.

Solution to the Rat in a maze Problem

We have discussed the main logic of the problem and now we need to wrap up all the above discussion to solve the actual problem.

In the actual Problem, we have to find the way as well as we have to specify the direction in which rat has to travel to reach the maze.

We will use string to store the directions and when we reach the destination, we will store that string to the vector and at last we will return that vector.

Let’s see the code for it,

Complete Code for C/C++

vector<string> s;

void dfs(int m[][MAX],int i,int j,int n,string st,int vis[][MAX])
{
    if(i < 0 || i >= n || j < 0 || j >= n) return;
    if(m[i][j] == 0 || vis[i][j] == 1) return;
    
    if(i == n-1 && j == n-1)
    {
        s.push_back(st);
        vis[i][j] = 0;
        return;
    }
    
    vis[i][j] = 1;
    
    st.push_back('U');
    dfs(m,i-1,j,n,st,vis);
    st.pop_back();
    
    st.push_back('D');
    dfs(m,i+1,j,n,st,vis);
    st.pop_back();
    
    st.push_back('L');
    dfs(m,i,j-1,n,st,vis);
    st.pop_back();
    
    st.push_back('R');
    dfs(m,i,j+1,n,st,vis);
    st.pop_back();
    
    vis[i][j] = 0;
    
    return;
    
}
vector<string> printPath(int m[MAX][MAX], int n)
{
    string st = "";
    s.clear();
    
    int vis[MAX][MAX];
    for(int i = 0;i<n;i++){
        for(int j=0;j<n;j++){
            vis[i][j] = 0;
        }
    }
    
    dfs(m,0,0,n,st,vis);
    sort(s.begin(),s.end());
    return s;
}

Note if no such path exists the function should return an empty vector. Don’t print (-1) for that case as it is clearly mentioned in the Problem Statement. The (-1) case will be handled by GFG.

I hope this explanation of rat in maze problem and working of Recursion are
clear to you all.

That’s all folks..!!!

Similar Problem : Find whether path exist

Tagged : /

Leave a Reply

Your email address will not be published. Required fields are marked *