Rat in a Maze | Backtracking using Stack | Java program to solve Rat in a maze problem with backtracking using stack ; default value for direction set to 0 ( Up ) ; maze of n * m matrix ; Driver code ; Initially setting the visited array to true ( unvisited ) ; Maze matrix ; Initially starting at ( 0 , 0 ) . ; Food coordinates Coordinates of food ; Pop the top node and move to the left , right , top , down or retract back according the value of node 's  dir variable. ; Increment the direction and push the node in the stack again . ; If we reach the Food coordinates return true ; Checking the Up direction . ; Checking the left direction ; Checking the down direction ; Checking the right direction ; If none of the direction can take the rat to the Food , retract back to the path where the rat came from . ; If the stack is empty and no path is found return false .
import java . util . Stack ; class Node { private int x , y ; private int dir ; public Node ( int i , int j ) { this . x = i ; this . y = j ; this . dir = 0 ; } public int getX ( ) { return x ; } public void setX ( int x ) { this . x = x ; } public int getY ( ) { return y ; } public void setY ( int y ) { this . y = y ; } public int getDir ( ) { return dir ; } public void setDir ( int dir ) { this . dir = dir ; } } public class RatInMaze { private static final int N = 4 ; private static final int M = 5 ; int n = N , m = M ; private static boolean [ ] [ ] visited = new boolean [ N ] [ M ] ; public static void main ( String [ ] args ) { setVisited ( true ) ; int maze [ ] [ ] = { { 1 , 0 , 1 , 1 , 0 } , { 1 , 1 , 1 , 0 , 1 } , { 0 , 1 , 0 , 1 , 1 } , { 1 , 1 , 1 , 1 , 1 } } ; if ( isReachable ( maze ) ) { System . out . println ( "Path Found!NEW_LINE"); } else System . out . println ( "No Path Found!NEW_LINE"); } private static void setVisited ( boolean b ) { for ( int i = 0 ; i < visited . length ; i ++ ) { for ( int j = 0 ; j < visited [ i ] . length ; j ++ ) { visited [ i ] [ j ] = b ; } } } private static boolean isReachable ( int maze [ ] [ ] ) { int i = 0 , j = 0 ; int fx , fy ; fx = 2 ; fy = 3 ; Stack < Node > s = new Stack < Node > ( ) ; Node temp = new Node ( i , j ) ; s . push ( temp ) ; while ( ! s . empty ( ) ) { temp = s . peek ( ) ; int d = temp . getDir ( ) ; i = temp . getX ( ) ; j = temp . getY ( ) ; temp . setDir ( temp . getDir ( ) + 1 ) ; s . pop ( ) ; s . push ( temp ) ; if ( i == fx && j == fy ) { return true ; } if ( d == 0 ) { if ( i - 1 >= 0 && maze [ i - 1 ] [ j ] == 1 && visited [ i - 1 ] [ j ] ) { Node temp1 = new Node ( i - 1 , j ) ; visited [ i - 1 ] [ j ] = false ; s . push ( temp1 ) ; } } else if ( d == 1 ) { if ( j - 1 >= 0 && maze [ i ] [ j - 1 ] == 1 && visited [ i ] [ j - 1 ] ) { Node temp1 = new Node ( i , j - 1 ) ; visited [ i ] [ j - 1 ] = false ; s . push ( temp1 ) ; } } else if ( d == 2 ) { if ( i + 1 < N && maze [ i + 1 ] [ j ] == 1 && visited [ i + 1 ] [ j ] ) { Node temp1 = new Node ( i + 1 , j ) ; visited [ i + 1 ] [ j ] = false ; s . push ( temp1 ) ; } } else if ( d == 3 ) { if ( j + 1 < M && maze [ i ] [ j + 1 ] == 1 && visited [ i ] [ j + 1 ] ) { Node temp1 = new Node ( i , j + 1 ) ; visited [ i ] [ j + 1 ] = false ; s . push ( temp1 ) ; } } else { visited [ temp . getX ( ) ] [ temp . getY ( ) ] = true ; s . pop ( ) ; } } return false ; } }