Minimum number of jumps to obtain an element of opposite parity | Bfs for odd numbers are source ; Initialize queue ; Stores for each node , the nodes visited and their distances ; If parity is 0 -> odd Otherwise -> even ; Perform multi - source bfs ; Extract the front element of the queue ; Traverse nodes connected to the current node ; If u is not visited ; If element with opposite parity is obtained ; Store its distance from source in ans [ ] ; Push the current neighbour to the queue ; Function to find the minimum jumps required by each index to reach element of opposite parity ; Initialise Inverse Graph ; Stores the result for each index ; For the jumped index ; If the ind is valid then add reverse directed edge ; Multi - source bfs with odd numbers as source by passing 0 ; Multi - source bfs with even numbers as source by passing 1 ; Print the answer ; Driver Code
def bfs ( n , a , invGr , ans , parity ) : NEW_LINE INDENT q = [ ] NEW_LINE vis = [ 0 for i in range ( n + 1 ) ] NEW_LINE dist = [ 0 for i in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( ( a [ i ] + parity ) & 1 ) : NEW_LINE INDENT q . append ( i ) NEW_LINE vis [ i ] = 1 NEW_LINE DEDENT DEDENT while ( len ( q ) != 0 ) : NEW_LINE INDENT v = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE for u in invGr [ v ] : NEW_LINE INDENT if ( not vis [ u ] ) : NEW_LINE INDENT dist [ u ] = dist [ v ] + 1 NEW_LINE vis [ u ] = 1 NEW_LINE if ( ( a [ u ] + parity ) % 2 == 0 ) : NEW_LINE INDENT if ( ans [ u ] == - 1 ) : NEW_LINE INDENT ans [ u ] = dist [ u ] NEW_LINE DEDENT DEDENT q . append ( u ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def minJumps ( a , jump , n ) : NEW_LINE INDENT invGr = [ [ ] for i in range ( n + 1 ) ] NEW_LINE ans = [ - 1 for i in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for ind in [ i + jump [ i ] , i - jump [ i ] ] : NEW_LINE INDENT if ( ind >= 1 and ind <= n ) : NEW_LINE INDENT invGr [ ind ] . append ( i ) NEW_LINE DEDENT DEDENT DEDENT bfs ( n , a , invGr , ans , 0 ) NEW_LINE bfs ( n , a , invGr , ans , 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( str ( ans [ i ] ) , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 0 , 4 , 2 , 5 , 2 , 1 ] NEW_LINE jump = [ 0 , 1 , 2 , 3 , 1 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE minJumps ( arr , jump , N - 1 ) NEW_LINE DEDENT