Minimize the number of steps required to reach the end of the array | Set 2 | Function to return the minimum steps required to reach the end of the given array ; Array to determine whether a cell has been visited before ; Queue for bfs ; Push the source i . e . index 0 ; Variable to store the depth of search ; BFS algorithm ; Current queue size ; Top - most element of queue ; Base case ; If we reach the destination i . e . index ( n - 1 ) ; Marking the cell visited ; Pushing the adjacent nodes i . e . indices reachable from the current index ; Driver code
def minSteps ( arr , n ) : NEW_LINE INDENT v = [ 0 for i in range ( n ) ] NEW_LINE q = [ ] NEW_LINE q . append ( 0 ) NEW_LINE depth = 0 NEW_LINE while ( len ( q ) != 0 ) : NEW_LINE INDENT x = len ( q ) NEW_LINE while ( x >= 1 ) : NEW_LINE INDENT i = q [ 0 ] NEW_LINE q . remove ( i ) NEW_LINE x -= 1 NEW_LINE if ( v [ i ] ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT if ( i == n - 1 ) : NEW_LINE INDENT return depth NEW_LINE DEDENT v [ i ] = 1 NEW_LINE if ( i + arr [ i ] < n ) : NEW_LINE INDENT q . append ( i + arr [ i ] ) NEW_LINE DEDENT if ( i - arr [ i ] >= 0 ) : NEW_LINE INDENT q . append ( i - arr [ i ] ) NEW_LINE DEDENT DEDENT depth += 1 NEW_LINE DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 1 , 1 , 1 , 1 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minSteps ( arr , n ) ) NEW_LINE DEDENT