@pabhinav30_5fbfffd82883f2cb compare your code with this approach and code :
If destination is reached print the solution matrix .
Else .
a) Mark current cell in solution matrix as 1.
b) Move forward in the horizontal direction and recursively check if this move leads to a solution.
c) If the move chosen in the above step doesn’t lead to a solution then move down and check if this move leads to a solution.
d) If none of the above solutions works then unmark this cell as 0 (BACKTRACK) and return false
Java
import java.util.*;
public class RatInMaze {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s=new Scanner(System.in);
/*char c=s.next().charAt(1);
System.out.println(c);*/
int m=s.nextInt();
int n=s.nextInt();
String[][] maze=new String[m][n];
int[][] v=new int[m][n];
int[][] sol=new int[m][n];
for(int i=0;i<m;i++)
{
String str=s.next();
for(int k=0;k<str.length();k++) {
char cc=str.charAt(k);
if(cc=='X') {
v[i][k]=1;
}
}
}
m--;
n--;
boolean ans =solveMaze(v,sol,0,0,m,n);
if(ans==false){
System.out.println("-1");
}
}
public static boolean solveMaze(int[][] v,int[][] sol,int i,int j,int m,int n) {
if(i==m && j==n){
sol[i][j] = 1;
///Print the soln
for(int x=0;x<=m;x++){
for(int y=0;y<=n;y++){
System.out.print(sol[x][y]+" ");
}
System.out.println();
}
return true;
}
if(v[i][j]==1)
return false;
v[i][j]=1;
///Recursive Case
///Assuming path exists from i,j
sol[i][j] = 1;
///1. Go Right
if(j+1<=n && v[i][j+1]==0){
boolean pathMila = solveMaze(v,sol,i,j+1,m,n);
if(pathMila==true){
return true;
}
}
/// 2. Go Down
if(i+1<=m && v[i+1][j]==0){
boolean pathMila = solveMaze(v,sol,i+1,j,m,n);
if(pathMila==true){
return true;
}
}
/// Yahan aane se path nahin mila !
///Backtracking
sol[i][j] = 0;
return false;
}
}