Shortest path for a thief to reach the Nth house avoiding policemen | C ++ program for the above approach ; Function to create graph edges where node A and B can be visited ; Visit all the connections ; If a policeman is at any point of connection , leave that connection . Insert the connect otherwise . ; Function to find the shortest path ; If police is at either at the 1 - st house or at N - th house ; The thief cannot reach the N - th house ; Stores Edges of graph ; Function call to store connections ; Stores wheather node is visited or not ; Stores distances from the root node ; Visit all nodes that are currently in the queue ; If current node is not visited already ; Driver Code ; N : Number of houses E : Number of edges ; Given positions ; Given Paths ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void createGraph ( unordered_map < int , vector < int > > & adj , int paths [ ] [ 2 ] , int A [ ] , int N , int E ) { for ( int i = 0 ; i < E ; i ++ ) { if ( ! A [ paths [ i ] [ 0 ] ] && ! A [ paths [ i ] [ 1 ] ] ) { adj [ paths [ i ] [ 0 ] ] . push_back ( paths [ i ] [ 1 ] ) ; } } } int minPath ( int paths [ ] [ 2 ] , int A [ ] , int N , int E ) { if ( A [ 0 ] == 1 A [ N - 1 ] == 1 ) return -1 ; unordered_map < int , vector < int > > adj ; createGraph ( adj , paths , A , N , E ) ; vector < int > visited ( N , 0 ) ; int dist [ N ] ; dist [ 0 ] = 0 ; queue < int > q ; q . push ( 0 ) ; visited [ 0 ] = 1 ; while ( ! q . empty ( ) ) { int temp = q . front ( ) ; q . pop ( ) ; for ( auto x : adj [ temp ] ) { if ( ! visited [ x ] ) { q . push ( x ) ; visited [ x ] = 1 ; dist [ x ] = dist [ temp ] + 1 ; } } } if ( ! visited [ N - 1 ] ) return -1 ; else return dist [ N - 1 ] ; } int main ( ) { int N = 5 , E = 5 ; int A [ ] = { 0 , 1 , 0 , 0 , 0 } ; int paths [ ] [ 2 ] = { { 0 , 1 } , { 0 , 2 } , { 1 , 4 } , { 2 , 3 } , { 3 , 4 } } ; cout << minPath ( paths , A , N , E ) ; return 0 ; }