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
#include <iostream> NEW_LINE using namespace std ; #define MAX  50 NEW_LINE bool hasPath ( int maze [ ] [ MAX ] , int sol [ ] [ MAX ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) sol [ i ] [ j ] = 0 ; bool * * CRF = new bool * [ N ] ; for ( int i = 0 ; i < N ; i ++ ) CRF [ i ] = new bool [ N ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) CRF [ i ] [ j ] = false ; CRF [ N - 1 ] [ N - 1 ] = true ; for ( int k = N - 1 ; k >= 0 ; k -- ) { for ( int 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 ; int 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 ; } void printMatrix ( int sol [ ] [ MAX ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) cout << sol [ i ] [ j ] << " ▁ " ; cout << " STRNEWLINE " ; } } int main ( ) { int maze [ ] [ MAX ] = { { 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 = sizeof ( maze ) / sizeof ( maze [ 0 ] ) ; int sol [ N ] [ MAX ] ; if ( hasPath ( maze , sol , N ) ) printMatrix ( sol , N ) ; else cout << " No ▁ path ▁ exists " ; return 0 ; }