Paths requiring minimum number of jumps to reach end of array | Python3 program to implement the above approach ; Pair Class instance ; Stores the current index ; Stores the path travelled so far ; Stores the minimum jumps required to reach the last index from current index ; Constructor ; 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 ; Stores the minimum jumps from each position to last position ; Driver Code
from queue import Queue NEW_LINE import sys NEW_LINE class Pair ( object ) : NEW_LINE INDENT idx = 0 NEW_LINE psf = " " NEW_LINE jmps = 0 NEW_LINE def __init__ ( self , idx , psf , jmps ) : NEW_LINE INDENT self . idx = idx NEW_LINE self . psf = psf NEW_LINE self . jmps = jmps NEW_LINE DEDENT DEDENT def minJumps ( arr ) : NEW_LINE INDENT MAX_VALUE = sys . maxsize NEW_LINE dp = [ MAX_VALUE for i in range ( len ( arr ) ) ] NEW_LINE n = len ( dp ) NEW_LINE dp [ n - 1 ] = 0 NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT steps = arr [ i ] NEW_LINE minimum = MAX_VALUE NEW_LINE for j in range ( 1 , steps + 1 , 1 ) : NEW_LINE INDENT if i + j >= n : NEW_LINE INDENT break NEW_LINE DEDENT if ( ( dp [ i + j ] != MAX_VALUE ) and ( dp [ i + j ] < minimum ) ) : NEW_LINE INDENT minimum = dp [ i + j ] NEW_LINE DEDENT DEDENT if minimum != MAX_VALUE : NEW_LINE INDENT dp [ i ] = minimum + 1 NEW_LINE DEDENT DEDENT return dp NEW_LINE DEDENT def possiblePath ( arr , dp ) : NEW_LINE INDENT queue = Queue ( maxsize = 0 ) NEW_LINE p1 = Pair ( 0 , "0" , dp [ 0 ] ) NEW_LINE queue . put ( p1 ) NEW_LINE while queue . qsize ( ) > 0 : NEW_LINE INDENT tmp = queue . get ( ) NEW_LINE if tmp . jmps == 0 : NEW_LINE INDENT print ( tmp . psf ) NEW_LINE continue NEW_LINE DEDENT for step in range ( 1 , arr [ tmp . idx ] + 1 , 1 ) : NEW_LINE INDENT if ( ( tmp . idx + step < len ( arr ) ) and ( tmp . jmps - 1 == dp [ tmp . idx + step ] ) ) : NEW_LINE INDENT p2 = Pair ( tmp . idx + step , tmp . psf + " ▁ - > ▁ " + str ( ( tmp . idx + step ) ) , tmp . jmps - 1 ) NEW_LINE queue . put ( p2 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def Solution ( arr ) : NEW_LINE INDENT dp = minJumps ( arr ) NEW_LINE possiblePath ( arr , dp ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 3 , 0 , 2 , 1 , 2 , 4 , 2 , 0 , 0 ] NEW_LINE size = len ( arr ) NEW_LINE Solution ( arr ) NEW_LINE DEDENT