(UVA) Frogger - Solution 2

If you want to see another solution for this problem, click here.

This solution is using Prim's algorithm.

The initial steps are the same used in the previous solution. The difference begins after sorting the array with the distances. Here, instead of calling the union-find method to connect each stone, I prepare an adjacency list and call the Prim method. In this method, I use almost the same approach used for Dijkstra, but instead of considering the weight of my current vertex plus the weight of all the other vertexes that I have already visited, I consider only the weight of my current vertex.


import java.io.*;
import java.util.*;
import java.text.DecimalFormat;

class Main  {
    public static ArrayList<Distance> distances;
    public static HashMap<Integer, Coord> map;
    public static HashMap<Integer, ArrayList<Edge>> adjList;

    public static Comparator<Edge> weightCompare = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            if ((e1.weight - e2.weight) < 0) {
                return -1;
            }
            else if ((e1.weight - e2.weight) > 0) {
                return 1;
            }
           
            return 0;
        }
    };
   
    public static double prim(int start, int end, int numStones) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numStones, weightCompare);
        Edge e = new Edge(start, 0.0);
        queue.add(e);
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        double maxJump = -1.0;
        while (queue.size() > 0) {
            Edge currEdge = queue.poll();
            int currStone = currEdge.stone;
            double currWeight = currEdge.weight;
            visited.add(currStone);
           
            if (currWeight > maxJump) {
                maxJump = currWeight;
            }
           
            if (currStone == end) {
                return maxJump;
            }
           
            ArrayList<Edge> reachableStones = adjList.get(currStone);
            for (int i = 0; i < reachableStones.size(); i++) {
                Edge next = reachableStones.get(i);
                if (!visited.contains(next.stone)) {
                    e = new Edge(next.stone, next.weight);
                    queue.add(e);
                }
            }
        }
       
        return -1;
    }
   
    public static void createAdjList() {
        for (int i = 0; i < distances.size(); i++) {
            int s1 = distances.get(i).source;
            int s2 = distances.get(i).dest;
            double d = distances.get(i).distance;
            Edge e = new Edge(s2, d);
            adjList.get(s1).add(e);
            e = new Edge(s1, d);
            adjList.get(s2).add(e);
        }
    }
   
    public static double dist(Coord c1, Coord c2) {
        return ((c1.x-c2.x)*(c1.x-c2.x)) + ((c1.y-c2.y)*(c1.y-c2.y));
    }
   
    public static void calcDist(Coord c1, int curr, int numStones) {
        for (int i = curr+1; i < numStones; i++) {
            if (i != curr) {
                Coord c2 = map.get(i);
                double dist = dist(c1, c2);
                Distance d = new Distance(curr, i, dist);
                distances.add(d);
            }
        }
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
       
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numStones = reader(br);
        int numCase = 0;
        while (numStones != 0) {
            distances = new ArrayList<Distance>();
            map = new HashMap<Integer, Coord>();
           
            int index = 0;
            int index2 = 0;
            for (int i = 0; i < numStones; i++) {
                int x = reader(br);
                int y = reader(br);
                Coord c = new Coord(x, y);
                map.put(index++, c);
            }
           
            for (int i = 0; i < numStones; i++) {
                calcDist(map.get(i), i, numStones);
            }
           
            Collections.sort(distances);

            adjList = new HashMap<Integer, ArrayList<Edge>>();
            for (int i = 0; i < numStones; i++) {
                adjList.put(i, new ArrayList<Edge>());
            }
            createAdjList();
           
            DecimalFormat df = new DecimalFormat("#.000");
            System.out.println("Scenario #" + ++numCase + "\nFrog Distance = " + df.format(Math.sqrt(prim(0, 1, numStones))) + "\n");
           
            numStones = reader(br);
        }
                 
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

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

class Distance implements Comparable<Distance> {
    int source;
    int dest;
    double distance;
   
    public Distance(int s, int d, double dist) {
        this.source = s;
        this.dest = d;
        this.distance = dist;
    }
   
    public int compareTo(Distance d) {
        double compareDist = d.distance;
       
        if ((this.distance - compareDist) < 0) {
            return -1;
        }
        else if ((this.distance - compareDist) > 0) {
            return 1;
        }
       
        return 0;
    }
}

class Edge {
    int stone;
    double weight;
   
    public Edge(int s, double w) {
        stone = s;
        weight = w;
    }
}