We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
staticintfindShortest(intgraphNodes,int[]graphFrom,int[]graphTo,long[]ids,intval){// Start by finding all nodes of the target color.List<Integer>targetNodes=newArrayList<Integer>();for(inth=0;h<ids.length;h++){if(ids[h]==val)targetNodes.add(h);}for(intx:targetNodes){System.out.println(x);}//Set up visited indicator and placeholder min. path lengths.boolean[]visited=newboolean[graphNodes];int[]pathLengths=newint[targetNodes.size()];for(intl=0;l<pathLengths.length;l++)pathLengths[l]=-1;//Create the graph in the form of a list of neighbor node lists.List<List<Integer>>neighbors=newArrayList<List<Integer>>();for(inti=0;i<graphNodes;i++)neighbors.add(newArrayList<Integer>());for(intj=0;j<graphFrom.length;j++){intnodeFrom=graphFrom[j]-1;intnodeTo=graphTo[j]-1;neighbors.get(nodeFrom).add(nodeTo);neighbors.get(nodeTo).add(nodeFrom);}//Reset the visited boolean array for each target node. Then use DFS to find the shortest path to the nearest node of the same color.for(intk=0;k<targetNodes.size();k++){visited=newboolean[graphNodes];intnode=targetNodes.get(k);//System.out.println("Node " + node);DFS(neighbors,visited,ids,val,0,pathLengths,k,node);}//Lastly, find the shortest path if present by sorting the array and looking for the first non-negative number.Arrays.sort(pathLengths);for(intm=0;m<pathLengths.length;m++){//System.out.println(pathLengths[m]);if(pathLengths[m]>0)returnpathLengths[m];}return-1;}staticvoidDFS(List<List<Integer>>neighbors,boolean[]visited,long[]ids,intval,intlen,int[]pathLengths,intnode,intcurr){//System.out.println("START: Node " + node);visited[curr]=true;List<Integer>nodeNeighbors=neighbors.get(curr);if(ids[curr]==val&&len>0){//If the function isn't at the starting node and the current node is of the target color, update the path length for the starting node. If the starting node already has a path length assigned, pick the minimum of len and the previous path length.//System.out.println("MATCH: Node " + curr);if(pathLengths[node]==-1){//System.out.println("ADD: Node " + node);pathLengths[node]=len;}else{//System.out.println("UPDATE: Node " + node);pathLengths[node]=Math.min(pathLengths[node],len);}}//Run the DFS function recursively with all neighbors that haven't been visited yet, adding 1 to the previous path length.for(intneighbor:nodeNeighbors){if(!visited[neighbor]){//System.out.println("Node " + curr + " (" + ids[curr] + "), Neighbor " + neighbor);DFS(neighbors,visited,ids,val,len+1,pathLengths,node,neighbor);}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Find the nearest clone
You are viewing a single comment's thread. Return to all comments →
Java 8 solution (passes all test cases):