Connect Islands with Smallest Amount of Bridges

Main.java

/* Problem:

N * M map, each tile can be of 2 types: water or land.

A map may contain several islands (connected land tiles). For example the following map has 3 islands.

   0 1 2 3 4 5 6
0 |.|x|x|.|.|.|.|
1 |.|.|.|.|.|.|x|
2 |.|.|x|x|x|.|x|
3 |.|.|.|.|.|.|.|
4 |.|.|.|.|.|x|x|

Now we want to build bridges to connect all the islands in the map and try to minimize the cost.
Step 1: determine "endpoints" to build bridges from. An endpoint is a piece of land surrounded by three waters.

   0 1 2 3 4 5 6
0 |.|O|O|.|.|.|.|
1 |.|.|.|.|.|.|O|
2 |.|.|O|.|O|.|O|
3 |.|.|.|.|.|.|.|
4 |.|.|.|.|.|O|O|

For example, in this case the endpoints are (0, 1), (0, 2), (1, 6), (2, 2), (2, 4), (2, 6), (4, 5), (4, 6). This is our graph to apply Prim's to.

Manhattan distances are then calculated. Representing in matrix form:
                      1          3
The bridges go from (0, 2) to (2, 2),
                      4          5
               from (2, 4) to (2, 6),
                      5          7
               from (2, 6) to (4, 6).

Step 2: these are points with cartesian coordinates, so we calculate the manhattan distance between all of them, and form a graph. This graph will be represented by an adjacency matrix with a "cut" (a diagonal with all zeroes which separates a symmetrical matrix). The nodes in this graph will correspond to each "endpoint", so in this case it's an 8 node graph. This graph is passed to the MST algorithm.

Input: n x m matrix
Ouput: Array[Pair[Pair[x1, y1], Pair[x2, y2]], Pair...] list of bridges

1. Parse matrix
2. Determine endpoints
3. Calculate distances between endpoints
4. Populate a graph with distances as weights
5. Calculate MST
*/

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.lang.Math;

class Main {
    public static List<List<Integer>> findEndpoints(char[][] map){
        int N = map.length;
        int M = map[0].length;
        List endpoints = new ArrayList();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(map[i][j] == 'x'){
                    int waters = 0;
                    //look up
                    if(i-1 < 0 || map[i-1][j] == '.'){
                        waters++;
                    }
                    //look down
                    if(i+1 >= N || map[i+1][j] == '.'){
                        waters++;
                    }
                    //look left
                    if(j-1 < 0 || map[i][j-1] == '.'){
                        waters++;
                    }
                    //look right
                    if(j+1 >= M || map[i][j+1] == '.'){
                        waters++;
                    }

                    if(waters >= 3){
                        endpoints.add(Arrays.asList(i, j));
                    }
                }
            }
        }
        return endpoints;
    }

    public static double manhattan(List<Integer> p1, List<Integer> p2){
        return Math.abs(p2.get(0) - p1.get(0)) + Math.abs(p2.get(1) - p1.get(1));
    }

    public static double[][] manhattanDistances(List<List<Integer>> endpoints){
        double[][] distances = new double[endpoints.size()][endpoints.size()];

        for(int i = 0; i < distances.length; i++){
            for(int j = 0; j < distances[0].length; j++){
                distances[i][j] = manhattan(endpoints.get(i), endpoints.get(j));
            }
        }

        return distances;
    }

    // grab the smallest possible value in the current key row
    public static int minKey(double[] key, Boolean[] visited){
        double min = Double.MAX_VALUE;
        int minIndex = -1;

        for(int i = 0; i < visited.length; i++){
            if(!visited[i] && key[i] < min){
                min = key[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    public static void printMST(double[][] graph){
        int[] parent = new int[graph.length];
        double[] key = new double[graph.length];
        Boolean[] visited = new Boolean[graph.length];

        for(int i = 0; i < graph.length; i++){
            visited[i] = false;
            key[i] = Double.MAX_VALUE;
        }

        key[0] = 0;
        parent[0] = -1;

        for(int count = 0; count < graph.length-1; count++){
            int u = minKey(key, visited);
            visited[u] = true;
            for(int i = 0; i < graph.length; i++){
                if(graph[u][i] != 0 && !visited[i] && graph[u][i] < key[i]){
                    parent[i] = u;
                    key[i] = graph[u][i];
                }
            }
        }

        System.out.println("Edge \tWeight");
        for (int i = 1; i < graph.length; i++)
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    }

    public static void main(String[] args) {
        char[][] map = new char[][]{
                new char[]{'.','x','x','.','.','.','.'},
                new char[]{'.','.','.','.','.','.','x'},
                new char[]{'.','.','x','x','x','.','x'},
                new char[]{'.','.','.','.','.','.','.'},
                new char[]{'.','.','.','.','.','x','x'},
        };
        List<List<Integer>> endpoints = findEndpoints(map);
        double[][] distances = manhattanDistances(endpoints);
        for(double[] row : distances) {
            System.out.println(Arrays.toString(row));
        }

        printMST(distances);
    }
}