//CODE 27:Rat in a maze
#include
#include
using namespace std;
//maze contains the maze
//solutions keep a track of the path
//i,j is the current index
//n,m is the size of the maze
bool ratInMaze(char maze[20][20], int solutions[20][20], int i, int j, int n, int m, string prev_move)
{
if(i==n-1 && j==m-1)
{
solutions[i][j] = 1;
//print the solution maze
for(int a=0; a<n; a++)
{
for(int b=0; b<m; b++)
{
cout<<solutions[a][b]<<" ";
}
cout<<endl;
}
// cout<<endl;
return true;
}
//check if still within the maze
if(i>=n || i<0) {return false;}
else if(j>=m || j<0) {return false;}
else if(maze[i][j]==‘X’){return false;}
//assume this is a solution path
solutions[i][j] = 1;
//try forward and downward
if(prev_move!="right")
{
bool left = ratInMaze(maze, solutions, i, j-1, n, m, "left");
if(left){return true;}
}
if(prev_move!="left")
{
bool right = ratInMaze(maze, solutions, i, j+1, n, m, "right");
if(right){return true;}
}
if(prev_move!="down")
{
bool up = ratInMaze(maze, solutions, i-1, j, n, m, "up");
if(up){return true;}
}
if(prev_move!="up")
{
bool down = ratInMaze(maze, solutions, i+1, j, n, m, "down");
if(down){return true;}
}
//backtracking
solutions[i][j] = 0;
return false;
}
int main() {
int row, column;
cin>>row>>column;
char maze[20][20];
for(int i=0; i<row; i++)
{
cin>>maze[i];
}
int solutions [20][20]{0};
bool found = ratInMaze(maze, solutions, 0, 0, row, column, “”);
if(found==false){cout<<“NO PATH FOUND”<<endl;}
}