//CODE 27:Rat in a maze
#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[1001][1001], int solutions[1001][1001], int i, int j, int n, int m)
{
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) {return false;}
else if(j>m) {return false;}
else if(maze[i][j]==‘X’){return false;}
//assume this is a solution path
solutions[i][j] = 1;
//try forward and downward
bool forward = ratInMaze(maze, solutions, i, j+1, n, m);
if(forward){return true;}
bool downward = ratInMaze(maze, solutions, i+1, j, n, m);
if(downward){return true;}
//backtracking
solutions[i][j] = 0;
// if(forward || downward)
// {
// return true;
// }
return false;
}
int main() {
int row, column;
cin>>row>>column;
char maze[1001][1001];
for(int i=0; i<row; i++)
{
cin>>maze[i];
}
int solutions [1001][1001]{0};
bool found = ratInMaze(maze, solutions, 0, 0, row, column);
if(found==false){cout<<-1<<endl;}
}