(UVA) Gopher and Hawks - Solution

I used Breadth-First Search to solve this problem.

First, I find all the possible paths that the gopher can take without being caught by the hawk. Then, I do the BFS in order to check if the gopher can go through the start hole to the target hole.


import java.io.*;
import java.util.*;

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> adjList;
    public static ArrayList<Coord> coords;
    public static int gophersSpeed;
    public static int maxTime;
   
   
    public static int bfs(int start, int target) {
        Queue<Path> queue = new ArrayDeque<Path>();
        queue.add(new Path(start, 0));
       
        HashSet<Integer> addedToQueue = new HashSet<Integer>();
        addedToQueue.add(start);
       
        while (queue.size() > 0) {
            Path curr = queue.poll();
            int currCoord = curr.coordIndex;
            int numHoles = curr.holes;
                       
            if (coords.get(currCoord).x == coords.get(target).x && coords.get(currCoord).y == coords.get(target).y) {
                return numHoles-1;
            }
           
            ArrayList<Integer> reachHoles = adjList.get(currCoord);
            for (int i = 0; i < reachHoles.size(); i++) {
                if (!addedToQueue.contains(reachHoles.get(i))) {
                    queue.add(new Path(reachHoles.get(i), numHoles+1));
                    addedToQueue.add(reachHoles.get(i));
                }
            }
        }
       
        return -1;
    }
     
    public static double dist(Coord c1, Coord c2) {
        return (c2.x-c1.x)*(c2.x-c1.x)+(c2.y-c1.y)*(c2.y-c1.y);
    }
 
    public static void drawGraph() {
        for (int i = 0; i < coords.size(); i++) {
            for (int j = i+1; j < coords.size(); j++) {
                double d = dist(coords.get(i), coords.get(j));
                if (d <= (60*gophersSpeed*maxTime)*(60*gophersSpeed*maxTime)) {
                    adjList.get(i).add(j);
                    adjList.get(j).add(i);
                }
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {  
        Scanner sc = new Scanner(System.in);
       
        gophersSpeed = sc.nextInt();
        maxTime = sc.nextInt();
        while (gophersSpeed != 0 || maxTime != 0) {
            coords = new ArrayList<Coord>();
            int index = 0;
           
            double startX = sc.nextDouble();
            double startY = sc.nextDouble();
            Coord start = new Coord(startX, startY);
            coords.add(start);
                       
            double targetX = sc.nextDouble();
            double targetY = sc.nextDouble();
            Coord target = new Coord(targetX, targetY);
            coords.add(target);
           
            String line = sc.nextLine();
            line = sc.nextLine();
            while (!line.equals("")) {
                String[] s = line.split("\\s");
                double x = Double.parseDouble(s[0]);
                double y = Double.parseDouble(s[1]);
                coords.add(new Coord(x, y));
                line = sc.nextLine();
            }
           
            adjList = new HashMap<Integer, ArrayList<Integer>>();
            for (int i = 0; i < coords.size(); i++) {
                adjList.put(i, new ArrayList<Integer>());
            }
            drawGraph();
           
            int numHoles = bfs(0, 1);
            if (numHoles == -1) {
                System.out.println("No.");
            }
            else {
                System.out.println("Yes, visiting " + numHoles + " other holes.");
            }
           
            gophersSpeed = sc.nextInt();
            maxTime = sc.nextInt();
        }
                                               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Coord {
    double x;
    double y;
   
    public Coord(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

class Path {
    int coordIndex;
    int holes;
   
    public Path(int coordIndex, int holes) {
        this.coordIndex = coordIndex;
        this.holes = holes;
    }
}