Rat In A Maze Using C++ [Easy Guide]

Filed Under: C++
Rat In A Maze Using C

Today we will learn to solve the rat in a maze problem using C++. It is a very interesting and popular interview question that involves recursion and backtracking. So without any further delay let’s move to the problem statement.

Problem Statement

You are given a M x N matrix, with some cells as blocked, you have to:

  • The rat is standing at the position: (0, 0)
  • Print all the possible paths from the source to the destination
  • Given that the rat can only move in
    • the forward direction(right) or
    • the downward direction(down)

Our task is to find all the ways out of the grid.

Concept of the Rat In A Maze Problem

Alright, let’s start with the concept. To solve this problem, you must imagine what’s going on at each stage. When dealing with recursion problems, we try to divide the bigger problem into smaller subproblems. The subproblems are further divided until we reach the base case.

Base Case: It is such a small problem whose solution is directly available.

Suppose the grid extends from: (0, 0) to (M – 1, N – 1)

Below are the steps that we will follow to find a way out of the grid.

  • At each cell we just have two choices
    • Either we move right
    • Or we move down
  • If we move right
    • Our grid effectively becomes: (0, 1) to (M – 1, N – 1)
  • Or if we move left
    • Now the effective grid boils down to: (1, 0) to (M – 1, N – 1)
  • Base Case: When the grid becomes (M – 1, N – 1) to (M – 1, N – 1)
    • This indicates that we have found a way out of the grid.
    • All that’s left now is to print the path(Backtrack)
  • We will create a boolean function that will tell us if a path on the right exists or not.
  • Similarly we will check for the paths using the downward cell.
  • We will call on both the functions to check for all possible paths
Algorithm 3
Algorithm

How Do We Store The Path?

One way of doing this is by using an additional boolean grid. We will mark the cell we are currently standing at true. But, it is also possible that the current path might not lead us to a solution. To tackle this situation, we will use backtracking.

  • Mark the cell we are currently standing at as true.
  • Check if there’s a way out using the right cell.
  • Similarly check if there’s a way out using the downward cell.
  • If both the cases returns false, mark current cell as false, and backtrack to the previous cell.(Dead ends)
  • The problem is not over yet. Once we find a way out, we will print the path.
  • While printing the path, we will mark the cell as false again, so that we can discover all the other paths as well.

Enough of talking, let’s quickly have a look at the code.

Implementing Rat In A Maze Using C++

#include <iostream>

using namespace std;

bool rat_in_a_maze(char maze[10][10], bool solution[10][10], int i, int j, int M, int N)
{
	// base case
	if(i == M && j == N)
	{
		// mark this cell as true
		solution[i][j] = true;

		// print this path
		for(int a = 0; a <= M; a++)
		{
			for(int b = 0; b <= N; b++)
			{
				cout << solution[a][b] << " ";
			}
			cout << endl;
		}
		cout << endl;

		// since the path exists
		// return true
		return true;
	}

	// recursive case
	// rat should be inside the grid
	if(i > M || j > N)
		return false;

	// the cell should not be blocked
	if(maze[i][j] == 'X')
		return false;

	// otherwise, we will assume that
	// a solution using this cell exists	
	solution[i][j] = true;

	// recursive calls
	bool right = rat_in_a_maze(maze, solution, i, j + 1, M, N);
	bool down = rat_in_a_maze(maze, solution, i + 1, j, M, N);

	// backtrack by marking this cell
	// as false again
	solution[i][j] = false;

	if(right || down)
		return true;

	// return false
	return false;
}

int main()
{
	// grid
	char maze[10][10] = {"0000", "00X0", "000X", "0X00"};

	// solution matrix
	bool solution[10][10] = {0};

	int M = 4, N = 4;
	bool ans = rat_in_a_maze(maze, solution, 0, 0, M, N);

	if(!ans)
		cout << "Path doesn't exist" << endl;
}

Output

Rat In A Maze Output
Rat In A Maze Output

Conclusion

In this article, we learned to solve the rat in a maze problem. We solved this problem using the concept of recursion and backtracking. Without using backtracking, we can not store all the possible paths out of the maze. In the end, we developed a C++ program to demonstrate this algorithm. That’s all for today, thanks for reading.

Further Readings

To learn more about recursion you can refer to the following articles

https://www.journaldev.com/56918/0-1-knapsack-using-cpp

https://www.journaldev.com/56866/solving-0-n-knapsack-problem-in-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content