Rat in a Maze Problem when movement in all possible directions is allowed | Java implementation of the above approach ; Vector to store all the possible paths ; Function returns true if the move taken is valid else it will return false . ; Function to print all the possible paths from ( 0 , 0 ) to ( n - 1 , n - 1 ) . ; This will check the initial point ( i . e . ( 0 , 0 ) ) to start the paths . ; If reach the last cell ( n - 1 , n - 1 ) then store the path and return ; Mark the cell as visited ; Check if downward move is valid ; Check if the left move is valid ; Check if the right move is valid ; Check if the upper move is valid ; Mark the cell as unvisited for other possible paths ; Function to store and print all the valid paths ; Call the utility function to find the valid paths ; Print all possible paths ; Driver code
import java . util . * ; class GFG { static Vector < String > possiblePaths = new Vector < > ( ) ; static String path = " " ; static final int MAX = 5 ; static boolean isSafe ( int row , int col , int m [ ] [ ] , int n , boolean visited [ ] [ ] ) { if ( row == - 1 row == n col == - 1 col == n visited [ row ] [ col ] m [ row ] [ col ] == 0 ) return false ; return true ; } static void printPathUtil ( int row , int col , int m [ ] [ ] , int n , boolean visited [ ] [ ] ) { if ( row == - 1 row == n col == - 1 col == n visited [ row ] [ col ] m [ row ] [ col ] == 0 ) return ; if ( row == n - 1 && col == n - 1 ) { possiblePaths . add ( path ) ; return ; } visited [ row ] [ col ] = true ; if ( isSafe ( row + 1 , col , m , n , visited ) ) { path += ' D ' ; printPathUtil ( row + 1 , col , m , n , visited ) ; path = path . substring ( 0 , path . length ( ) - 1 ) ; } if ( isSafe ( row , col - 1 , m , n , visited ) ) { path += ' L ' ; printPathUtil ( row , col - 1 , m , n , visited ) ; path = path . substring ( 0 , path . length ( ) - 1 ) ; } if ( isSafe ( row , col + 1 , m , n , visited ) ) { path += ' R ' ; printPathUtil ( row , col + 1 , m , n , visited ) ; path = path . substring ( 0 , path . length ( ) - 1 ) ; } if ( isSafe ( row - 1 , col , m , n , visited ) ) { path += ' U ' ; printPathUtil ( row - 1 , col , m , n , visited ) ; path = path . substring ( 0 , path . length ( ) - 1 ) ; } visited [ row ] [ col ] = false ; } static void printPath ( int m [ ] [ ] , int n ) { boolean [ ] [ ] visited = new boolean [ n ] [ MAX ] ; printPathUtil ( 0 , 0 , m , n , visited ) ; for ( int i = 0 ; i < possiblePaths . size ( ) ; i ++ ) System . out . print ( possiblePaths . get ( i ) + " ▁ " ) ; } public static void main ( String [ ] args ) { int m [ ] [ ] = { { 1 , 0 , 0 , 0 , 0 } , { 1 , 1 , 1 , 1 , 1 } , { 1 , 1 , 1 , 0 , 1 } , { 0 , 0 , 0 , 0 , 1 } , { 0 , 0 , 0 , 0 , 1 } } ; int n = m . length ; printPath ( m , n ) ; } }