A variation of Rat in a Maze : multiple steps or jumps allowed | JavaScript implementation of the approach ; Function to check whether the path exists ; Declaring and initializing CRF ( can reach from ) matrix ; Using the DP to fill CRF matrix in correct order ; If it is possible to get to a valid location from cell maze [ k ] [ j ] ; If it is possible to get to a valid location from cell maze [ j ] [ k ] ; If CRF [ 0 ] [ 0 ] is false it means we cannot reach the end of the maze at all ; Filling the solution matrix using CRF ; Get to a valid location from the current cell ; Utility function to print the contents of a 2 - D array ; Driver code ; If path exists ; Print the path
var MAX = 50 ; function hasPath ( maze , sol , N ) { for ( var i = 0 ; i < N ; i ++ ) for ( var j = 0 ; j < N ; j ++ ) sol [ i ] [ j ] = 0 ; var CRF = Array . from ( Array ( N ) , ( ) => Array ( N ) ) ; ; for ( var i = 0 ; i < N ; i ++ ) for ( var j = 0 ; j < N ; j ++ ) CRF [ i ] [ j ] = false ; CRF [ N - 1 ] [ N - 1 ] = true ; for ( var k = N - 1 ; k >= 0 ; k -- ) { for ( var j = k ; j >= 0 ; j -- ) { if ( ! ( k == N - 1 && j == N - 1 ) ) { for ( var a = 0 ; a <= maze [ k ] [ j ] ; a ++ ) { if ( ( j + a < N && CRF [ k ] [ j + a ] == true ) || ( k + a < N && CRF [ k + a ] [ j ] == true ) ) { CRF [ k ] [ j ] = true ; break ; } } for ( var a = 0 ; a <= maze [ j ] [ k ] ; a ++ ) { if ( ( k + a < N && CRF [ j ] [ k + a ] == true ) || ( j + a < N && CRF [ j + a ] [ k ] == true ) ) { CRF [ j ] [ k ] = true ; break ; } } } } } if ( CRF [ 0 ] [ 0 ] == false ) return false ; var i = 0 , j = 0 ; while ( ! ( i == N - 1 && j == N - 1 ) ) { sol [ i ] [ j ] = 1 ; if ( maze [ i ] [ j ] > 0 ) for ( var a = 1 ; a <= maze [ i ] [ j ] ; a ++ ) { if ( ( j + a < N && CRF [ i ] [ j + a ] == true ) ) { j = j + a ; break ; } else if ( ( i + a < N && CRF [ i + a ] [ j ] == true ) ) { i = i + a ; break ; } } } sol [ N - 1 ] [ N - 1 ] = 1 ; return true ; } function printMatrix ( sol , N ) { for ( var i = 0 ; i < N ; i ++ ) { for ( var j = 0 ; j < N ; j ++ ) document . write ( sol [ i ] [ j ] + " " ) ; document . write ( " " ) ; } } var maze = [ [ 2 , 2 , 1 , 1 , 0 ] , [ 0 , 0 , 3 , 0 , 0 ] , [ 1 , 0 , 0 , 0 , 0 ] , [ 0 , 0 , 2 , 0 , 1 ] , [ 0 , 0 , 3 , 0 , 0 ] ] ; var N = maze . length ; var sol = Array . from ( Array ( N ) , ( ) => Array ( MAX ) ) ; if ( hasPath ( maze , sol , N ) ) printMatrix ( sol , N ) ; else document . write ( " " ) ;