Paths requiring minimum number of jumps to reach end of array | C ++ program to implement the above approach ; Pair Struct ; Stores the current index ; Stores the path travelled so far ; Stores the minimum jumps required to reach the last index from current index ; Minimum jumps required to reach end of the array ; Stores the maximum number of steps that can be taken from the current index ; Checking if index stays within bounds ; Stores the minimum number of jumps required to jump from ( i + j ) - th index ; Function to find all possible paths to reach end of array requiring minimum number of steps ; Storing the neighbours of current index element ; Function to find the minimum steps and corresponding paths to reach end of an array ; dp [ ] array stores the minimum jumps from each position to last position ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Pair { int idx ; string psf ; int jmps ; } ; void minJumps ( int arr [ ] , int dp [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) dp [ i ] = INT_MAX ; dp [ n - 1 ] = 0 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int steps = arr [ i ] ; int min = INT_MAX ; for ( int j = 1 ; j <= steps && i + j < n ; j ++ ) { if ( dp [ i + j ] != INT_MAX && dp [ i + j ] < min ) { min = dp [ i + j ] ; } } if ( min != INT_MAX ) dp [ i ] = min + 1 ; } } void possiblePath ( int arr [ ] , int dp [ ] , int n ) { queue < Pair > Queue ; Pair p1 = { 0 , "0" , dp [ 0 ] } ; Queue . push ( p1 ) ; while ( Queue . size ( ) > 0 ) { Pair tmp = Queue . front ( ) ; Queue . pop ( ) ; if ( tmp . jmps == 0 ) { cout << tmp . psf << " STRNEWLINE " ; continue ; } for ( int step = 1 ; step <= arr [ tmp . idx ] ; step ++ ) { if ( tmp . idx + step < n && tmp . jmps - 1 == dp [ tmp . idx + step ] ) { string s1 = tmp . psf + " ▁ - > ▁ " + to_string ( ( tmp . idx + step ) ) ; Pair p2 = { tmp . idx + step , s1 , tmp . jmps - 1 } ; Queue . push ( p2 ) ; } } } } void Solution ( int arr [ ] , int dp [ ] , int size ) { minJumps ( arr , dp , size ) ; possiblePath ( arr , dp , size ) ; } int main ( ) { int arr [ ] = { 3 , 3 , 0 , 2 , 1 , 2 , 4 , 2 , 0 , 0 } ; int size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int dp [ size ] ; Solution ( arr , dp , size ) ; }