(UVA) Bear with me, again.. - Solution 2

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=1888

If you want to see another solution for this problem using Floyd-Warshall, click here.

The solution below used Breadth-First Search (BFS) to solve this problem. We first calculate the distance between every pair of island. If the travel between these islands takes less days than it is allowed, we consider this path in our adjacency list. Finally, we call a BFS method to check if it is possible to go from the start island to the desired destination.


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

class Main {
    public ArrayList<ArrayList<Integer>> adjList;
   
    public int bfs(int start, int end) {
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.add(start);
       
        HashSet<Integer> visited = new HashSet<>();
       
        while (queue.size() > 0) {
            int currNode = queue.poll();
           
            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);
           
            if (currNode == end) {
                return 1;
            }
           
            ArrayList<Integer> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                queue.add(reachNodes.get(i));
            }
        }
       
        return -1;
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        while (sc.hasNext()) {
            int numDays = sc.nextInt(); // max number of days they can stay in the sea
            int speed = sc.nextInt(); // miles a day
           
            ArrayList<Info> coordinates = new ArrayList<>();
            coordinates.add(new Info(0, sc.nextInt(), sc.nextInt(), sc.nextInt())); // start
            coordinates.add(new Info(1, sc.nextInt(), sc.nextInt(), sc.nextInt())); // end
           
            int numIntermediateIslands = sc.nextInt();
            int numTotalIslands = numIntermediateIslands+2;
            for (int i = 2; i < numTotalIslands; i++) { // read coordinates of intermediate islands
                coordinates.add(new Info(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
            }
           
            adjList = new ArrayList<>();
            for (int i = 0; i < numTotalIslands; i++) {
                adjList.add(new ArrayList<Integer>());
            }
           
            // calculate the distance between each pair of island
            for (int i = 0; i < numTotalIslands; i++) {       
                for (int j = i+1; j < numTotalIslands; j++) {
                    // distance between two islands / minus the radius of both islands / it results in how many miles they are distant / divide it by the speed
                    // result: how many days to go from one island to the other
                    double days = (Math.sqrt((coordinates.get(i).x-coordinates.get(j).x)*(coordinates.get(i).x-coordinates.get(j).x)+(coordinates.get(i).y-coordinates.get(j).y)*(coordinates.get(i).y-coordinates.get(j).y)) - coordinates.get(i).radius - coordinates.get(j).radius)/speed;       
                    if (days > numDays) {
                        continue;
                    }
                    adjList.get(i).add(j);
                    adjList.get(j).add(i);
                }
            }

            int result = bfs(0, 1); // 0 = start, 1 = end

            if (result == 1) {
                bw.write("Larry and Ryan will escape!\n");       
            }
            else {
                bw.write("Larry and Ryan will be eaten to death.\n");
            }       
        }
                       
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Info {
    int id;
    int x;
    int y;
    int radius;
   
    public Info(int id, int x, int y, int radius) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.radius = radius;
    }
}