Rat in a Maze Problem when movement in all possible directions is allowed | 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
let possiblePaths = [ ] ; let path = " " ; let MAX = 5 ; function isSafe ( row , col , m , n , visited ) { if ( row == - 1 row == n col == - 1 col == n visited [ row ] [ col ] m [ row ] [ col ] == 0 ) return false ; return true ; } function printPathUtil ( row , col , m , n , 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 . push ( path ) ; return ; } visited [ row ] [ col ] = true ; if ( isSafe ( row + 1 , col , m , n , visited ) ) { path += ' ' ; printPathUtil ( row + 1 , col , m , n , visited ) ; path = path . substring ( 0 , path . length - 1 ) ; } if ( isSafe ( row , col - 1 , m , n , visited ) ) { path += ' ' ; printPathUtil ( row , col - 1 , m , n , visited ) ; path = path . substring ( 0 , path . length - 1 ) ; } if ( isSafe ( row , col + 1 , m , n , visited ) ) { path += ' ' ; printPathUtil ( row , col + 1 , m , n , visited ) ; path = path . substring ( 0 , path . length - 1 ) ; } if ( isSafe ( row - 1 , col , m , n , visited ) ) { path += ' ' ; printPathUtil ( row - 1 , col , m , n , visited ) ; path = path . substring ( 0 , path . length - 1 ) ; } visited [ row ] [ col ] = false ; } function printPath ( m , n ) { let visited = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { visited [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) visited [ i ] [ j ] = false ; } printPathUtil ( 0 , 0 , m , n , visited ) ; for ( let i = 0 ; i < possiblePaths . length ; i ++ ) document . write ( possiblePaths [ i ] + " " ) ; } let 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 ] ] ; let n = m . length ; printPath ( m , n ) ;