Rat in a Maze with C++

Rat in a Maze is a popular problem of coding interviews based on Backtracking algorithm. In this article, I will take you through a solution to Rat in a Maze with C++ programming language.

rat in a maze

What is Backtracking?

A backtracking algorithm attempts to build a solution to a computational problem incrementally, one small piece at a time. Whenever the algorithm needs to decide between several alternatives to the next component of the solution, it recursively evaluates each alternative and then chooses the best one.

Also, Read – 100+ Machine Learning Projects Solved and Explained.

Simply put, backtracking is a recursive technique, which attempts to solve problems by assuming parts of the solution. After assuming the first part of the solution, we move on to assume the second part of the solution and so on. If we are lucky, all of the assumptions we made form a complete solution and the problem is solved.

On the other hand, if the chosen path does not return a solution, then we go back. This means that we undo the last part of the solution we assumed and try another. This continues until we find a solution, or try all the possibilities and see that a solution does not exist.

Rat in a Maze with C++

Now, in this section, I will solve a problem known as a rat in a maze with C++ programming language. Rat in a Maze is a very popular problem for backtracking in coding interviews. 

Here I will solve the problem of Rat in a Maze by using C++ programming language. Let’s have a look at our problem statement below.

Rat in a Maze Problem Statement

You receive an N*N maze with a rat placed in maze [0] [0]. Using the C++ programming language, find and print all the paths that rat can follow to reach its destination, ie the maze [N-1] [N-1]. The rat can move in any direction (left, right, up and down). The value of each cell in the maze can be 0 or 1. Cells with value 0 are blocked means rat cannot enter those cells and those with value 1 are open.

Solving Rat in a Maze with C++ programming language:

#include<iostream>
using namespace std;

bool issafe(int** arr, int x, int y, int n){
    if(x<n && y<n && arr[x][y]==1){
        return true;
    }
    return false;
}
bool ratinMaze(int** arr, int x, int y, int n, int** solArr){
    if(x==n-1 && y==n-1){
        solArr[x][y]=1;
        return true;
    }
    if(issafe(arr, x, y, n)){
        solArr[x][y]=1;
        if(ratinMaze(arr, x+1, y, n, solArr)){
            return true;
        }
        if(ratinMaze(arr, x, y+1, n, solArr)){
            return true;
        }
        solArr[x][y]=0;
        return false;
    }
    return false;
}
int main(){
    int n;
    cin>>n;
    int** arr=new int*[n];
    for(int i=0; i<n; i++){
        arr[i]=new int[n];
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>arr[i][j];
        }
    }
    int** solArr=new int*[n];
    for(int i=0; i<n; i++){
        solArr[i] = new int[n];
        for(int j=0; j<n; j++){
            solArr[i][j]=0;
        }
    }
    if(ratinMaze(arr, 0, 0, n, solArr)){
        for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout<<solArr[i][j];
        }cout<<endl;

        }
    }
    return 0;
}
5
1 0 1 0 1
1 1 1 1 1
0 1 0 1 0
1 0 0 1 1
1 1 1 0 1
10000
11110
00010
00011
00001

I hope you liked this article on solving rat in a maze with C++ programming language. It is a very popular problem statement in coding interviews. Feel free to ask your valuable questions in the comments section below.

Aman Kharwal
Aman Kharwal

I'm a writer and data scientist on a mission to educate others about the incredible power of data📈.

Articles: 1498

Leave a Reply