Minimum number of jumps to obtain an element of opposite parity | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void bfs ( int n , vector < int > & a , vector < int > invGr [ ] , vector < int > & ans , int parity ) { queue < int > q ; vector < int > vis ( n + 1 , 0 ) ; vector < int > dist ( n + 1 , 0 ) ; for ( int i = 1 ; i <= n ; i ++ ) { if ( ( a [ i ] + parity ) & 1 ) { q . push ( i ) ; vis [ i ] = 1 ; } } while ( ! q . empty ( ) ) { int v = q . front ( ) ; q . pop ( ) ; for ( int u : invGr [ v ] ) { if ( ! vis [ u ] ) { dist [ u ] = dist [ v ] + 1 ; vis [ u ] = 1 ; if ( ( a [ u ] + parity ) % 2 == 0 ) { if ( ans [ u ] == -1 ) ans [ u ] = dist [ u ] ; } q . push ( u ) ; } } } } void minJumps ( vector < int > & a , vector < int > & jump , int n ) { vector < int > invGr [ n + 1 ] ; vector < int > ans ( n + 1 , -1 ) ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int ind : { i + jump [ i ] , i - jump [ i ] } ) { if ( ind >= 1 and ind <= n ) { invGr [ ind ] . push_back ( i ) ; } } } bfs ( n , a , invGr , ans , 0 ) ; bfs ( n , a , invGr , ans , 1 ) ; for ( int i = 1 ; i <= n ; i ++ ) { cout << ans [ i ] << ' ▁ ' ; } } int main ( ) { vector < int > arr = { 0 , 4 , 2 , 5 , 2 , 1 } ; vector < int > jump = { 0 , 1 , 2 , 3 , 1 , 2 } ; int N = arr . size ( ) ; minJumps ( arr , jump , N - 1 ) ; return 0 ; }