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.

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.

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;
}

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.