A variation of Rat in a Maze : multiple steps or jumps allowed | C # 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
using System ; class GFG { static int MAX = 50 ; static Boolean hasPath ( int [ , ] maze , int [ , ] sol , int N ) { int i , j , k ; for ( i = 0 ; i < N ; i ++ ) for ( j = 0 ; j < N ; j ++ ) sol [ i , j ] = 0 ; Boolean [ , ] CRF = new Boolean [ N , N ] ; CRF [ N - 1 , N - 1 ] = true ; for ( k = N - 1 ; k >= 0 ; k -- ) { for ( j = k ; j >= 0 ; j -- ) { if ( ! ( k == N - 1 && j == N - 1 ) ) { for ( int 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 ( int 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 ; i = 0 ; j = 0 ; while ( ! ( i == N - 1 && j == N - 1 ) ) { sol [ i , j ] = 1 ; if ( maze [ i , j ] > 0 ) for ( int 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 ; } static void printMatrix ( int [ , ] sol , int N ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) Console . Write ( sol [ i , j ] + " ▁ " ) ; Console . WriteLine ( ) ; } } public static void Main ( String [ ] args ) { int [ , ] 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 } } ; int N = maze . GetLength ( 0 ) ; int [ , ] sol = new int [ N , MAX ] ; if ( hasPath ( maze , sol , N ) ) printMatrix ( sol , N ) ; else Console . WriteLine ( " No ▁ path ▁ exists " ) ; } }