Rat in a maze is a common question asked in interviews of tech companies in placements as well as internships. In this post we will study the algorithm used and provide relevant code in C language.
The question is : Given a maze represented in matrix form, find a path from the source to the destination. The source will be the first element , i.e., first row - first column, and destination will be the last element, i.e., the last row and last column. An obstacle or invalid path will be denoted as 0, while a valid cell where you can move is denoted by 1. You are allowed to move in forward (right) and downward (down) directions only. This is the most basic and minimalistic problem based on maze. We can extend the problem to increase its complexity by providing variable sources and destinations, ability to move in all directions, etc.
In the following code we have used a recursive technique to find the solution matrix.
#include <iostream>
using namespace std;
int row, col;
void print(int maze[10][10])
{
int i,j;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
}
int valid(int maze[][10], int x, int y)
{
if(x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 1)
return 1;
return 0;
}
int find_path(int maze[10][10], int x, int y, int ans[10][10])
{
if(x==row-1 && y==col-1)
{
ans[x][y]=1;
print(ans);
return 1;
}
if(valid(maze, x, y))
{
ans[x][y] = 1;
if (find_path(maze, x+1, y,ans))
return 1;
if (find_path(maze, x, y+1, ans))
return 1;
ans[x][y] = 0;
return 0;
}
return 0;
}
int main()
{
int i,j,maze[10][10], ans[10][10];
cout << "\t\tThe rat maze problem\nEnter the maze matrix size: (rows columns)";
cin>>row>>col;
cout<<"Enter the maze matrix:\n";
for(i=0;i<row;i++)
for(j=0;j<col;j++)
cin>>maze[i][j],ans[i][j]=0;
find_path(maze,0,0,ans);
return 0;
}
To extend the code's functionalities, we can add additional if conditions for upward movement (find_path(maze, x-1, y, ans)), or leftward movement (find_path(maze, x, y-1, ans)). We can also extend it for any single source and any single destination by specifying the coordinates in base case.
