Rat In A Maze problem

#1

I am able to print all the solutions(possible paths) . Please guide me how can I print the one path only that is the right most path.
here is the code:-

#include
using namespace std;

bool ratInMaze(char maze[1000][1000],int sol[1000][1000],int i,int j,int m,int n){
// base case
if(i==m && j==n){
sol[m][n]=1;
// printing the sol array
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
cout<<sol[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
return true;
}

// rec case

/// rat out of the grid
if(i>m || j>>n){
    return false;
}
// if obstacle comes
if(maze[i][j]=='X'){
    return false;
}

sol[i][j]=1;

bool forwardSuccess=ratInMaze(maze,sol,i,j+1,m,n);
bool downSuccess=ratInMaze(maze,sol,i+1,j,m,n);

sol[i][j]=0;   // backtracking

if(forwardSuccess || downSuccess){
    return true;
}
return false;

}

int main() {
int m,n;
cin>>m>>n;
char maze[1000][1000];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>maze[i][j];
}
}
int sol[1000][1000]={0};

bool ans=ratInMaze(maze,sol,0,0,m-1,n-1);	

if(ans==false){
    cout<<"-1";
}

}

#2

@krikhi For that, instead of using these 2 lines in your code:
bool forwardSuccess=ratInMaze(maze,sol,i,j+1,m,n);
bool downSuccess=ratInMaze(maze,sol,i+1,j,m,n);

Use:
bool forwardSuccess=ratInMaze(maze,sol,i,j+1,m,n);
if(!forwardSuccess)
{
ratInMaze(maze,sol,i+1,j,m,n);
}

This will make sure that only when no possible path is there on moving right, you move down.

Hope this helps :slightly_smiling_face:

#3

i have done this but still some test cases are not getting passed. The link to the code is :- https://ide.codingblocks.com/s/170157