Rat in Maze problem : This is a famous problem solving coding question. There is a grid filled with 1 and 0, There is a rat at position 0,0. He has to reach at the last point of Grid and the Rat can move to block having value 1.
Print the path the will take to reach.
C++ Code for Rat in Maze Problem
#include <iostream>
using namespace std;
#define N 5
int path[N][N]={1,1,1,1,1,
0,0,1,0,1,
1,1,1,1,1,
1,0,1,0,0,
1,1,1,1,1
};
int sol[N][N];
bool isValid(int row,int col)
{
if(row>=0&&col>=0&&row<N&&col<N&&path[row][col]==1&&sol[row][col]==0)
return true;
else
return false;
}
bool solveRatInMaze(int row,int col)
{
if(row==N-1&&col==N-1)
{
sol[row][col]=1;
return true;
}
// int i=row,j= col;
if(isValid(row,col)==true)
{
sol[row][col]=1;
// move right
if(solveRatInMaze(row+1,col)==true)
return true;
if(solveRatInMaze(row,col+1)==true)
return true;
if(solveRatInMaze(row+1,col)==true)
return true;
if(solveRatInMaze(row-1,col)==true)
return true;
if(solveRatInMaze(row,col-1)==true)
return true;
sol[row][col]=0;
}
else
return false;
return false;
}
int main(int argc, char *argv[])
{
int i,j;
for( i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
sol[i][j]=0;
}
}
if(solveRatInMaze(0,0)==true)
{
for( i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
printf("%d ",sol[i][j]);
}
printf("\n");
}
}
else
printf("There is no path");
return EXIT_SUCCESS;
}
Output :
1 1 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 1 1
