Shortest path for a thief to reach the Nth house avoiding policemen | Java 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
import java . io . * ; import java . lang . * ; import java . util . * ; public class GFG { static void createGraph ( HashMap < Integer , ArrayList < Integer > > adj , int paths [ ] [ ] , int A [ ] , int N , int E ) { for ( int i = 0 ; i < E ; i ++ ) { if ( A [ paths [ i ] [ 0 ] ] != 1 && A [ paths [ i ] [ 1 ] ] != 1 ) { ArrayList < Integer > list = adj . getOrDefault ( paths [ i ] [ 0 ] , new ArrayList < > ( ) ) ; list . add ( paths [ i ] [ 1 ] ) ; adj . put ( paths [ i ] [ 0 ] , list ) ; } } } static int minPath ( int paths [ ] [ ] , int A [ ] , int N , int E ) { if ( A [ 0 ] == 1 A [ N - 1 ] == 1 ) return - 1 ; HashMap < Integer , ArrayList < Integer > > adj = new HashMap < > ( ) ; createGraph ( adj , paths , A , N , E ) ; boolean visited [ ] = new boolean [ N ] ; int dist [ ] = new int [ N ] ; dist [ 0 ] = 0 ; ArrayDeque < Integer > q = new ArrayDeque < > ( ) ; q . addLast ( 0 ) ; visited [ 0 ] = true ; while ( ! q . isEmpty ( ) ) { int temp = q . removeFirst ( ) ; for ( int x : adj . getOrDefault ( temp , new ArrayList < > ( ) ) ) { if ( ! visited [ x ] ) { q . addLast ( x ) ; visited [ x ] = true ; dist [ x ] = dist [ temp ] + 1 ; } } } if ( ! visited [ N - 1 ] ) return - 1 ; else return dist [ N - 1 ] ; } public static void main ( String [ ] args ) { int N = 5 , E = 5 ; int A [ ] = { 0 , 1 , 0 , 0 , 0 } ; int paths [ ] [ ] = { { 0 , 1 } , { 0 , 2 } , { 1 , 4 } , { 2 , 3 } , { 3 , 4 } } ; System . out . print ( minPath ( paths , A , N , E ) ) ; } }