(UVA) Frogger - Solution 3

If you want to see other solutions for this problem, click here and here.

This solution is using Prim's algorithm.

This solution is almost the same as the previous one using Prim. The difference here is that I am calculating the distance between two points inside the Prim method. Then, I do not need to have an adjacency list, and I also do not need to keep a list with the distances.


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

class Main  {
    public static HashMap<Integer, Coord> map;

    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;
            }
           
            for (int i = 0; i < numStones; i++) {
                if (i != currStone && !visited.contains(i)) {
                    e = new Edge(i, dist(map.get(currStone), map.get(i)));
                    queue.add(e);
                }
            }
        }
       
        return -1;
    }
   
    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 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) {
            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);
            }
           
            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;
    }
}