Create A Tiling Dino from Black and White Pixels n Java Assignment Solution

/**

 * CS4102 Spring 2022 -- Unit D Programming

 *********************************

 * Collaboration Policy: You are encouraged to collaborate with up to 3 other

 * students, but all work submitted must be your own independently written

 * solution. List the computing ids of all of your collaborators in the comment

 * at the top of your java or python file. Do not seek published or online

 * solutions for any assignments. If you use any published or online resources

 * (which may not include solutions) when completing this assignment, be sure to

 * cite them. Do not submit a solution that you are unable to explain orally to a

 * member of the course staff.

 *********************************

 * Your Computing ID:

 * Collaborators:

 * Sources: Introduction to Algorithms, Cormen

 **************************************/

import java.io.File;

import java.util.*;

public class TilingDino {

    private static class Edge {

        private final int from;

        private final int to;

        private int capacity;

        public Edge(int from, int to, int capacity) {

            this.from = from;

            this.to = to;

            this.capacity = capacity;

        }

    }

    private Object[] ff(Edge[][] graph, Mapmap) {

        int source = 0;

        int target = graph.length - 1;

        int flow = 0;

        List path = new ArrayList<>();

        Set visited = new HashSet<>();

        visited.add(source);

        while (dfs(graph, source, target, path, visited)) {

            int min = Integer.MAX_VALUE;

            for (Edge e : path) {

                if (e.capacity < min) {

                    min = e.capacity;

                }

            }

            flow += min;

            for (Edge e : path) {

                graph[e.from][e.to].capacity -= min;

                graph[e.to][e.from].capacity += min;

            }

            path.clear();

            visited.clear();

            visited.add(source);

        }

        List edges = new ArrayList<>();

        for (int i = source + 1; i

            Location location = map.get(i);

            if (!location.isEven()) {

                continue;

            }

            for (int j = source + 1; j

                if (graph[i][j] == null) {

                    continue;

                }

                else {

                    if (graph[i][j].capacity == 0) {

                        edges.add(graph[i][j]);

                    }

                }

            }

        }

        return new Object[]{flow, edges};

    }

    private boolean dfs(Edge[][] graph, int curr, int target, List path, Set visited) {

        if (curr == target) {

            return true;

        }

        for (int i = 0; i <= target; i++) {

            if (!visited.contains(i) && graph[curr][i] != null && graph[curr][i].capacity > 0) {

                visited.add(i);

                path.add(new Edge(curr, i, graph[curr][i].capacity));

                boolean result = dfs(graph, i, target, path, visited);

                if (result) {

                    return true;

                }

                path.remove(path.size() - 1);

            }

        }

        return false;

    }

    /**

     * This is the method that should set off the computation

     * of tiling dino. It takes as input a list lines of input

     * as strings. You should parse that input, find a tiling,

     * and return a list of strings representing the tiling

     *

     * @return the list of strings representing the tiling

     */

    public List compute(List fileLines) {

        List result = new ArrayList<>();

        int rows = fileLines.size();

        int cols = fileLines.get(0).length();

        char[][] map = new char[rows][cols];

        for (int i = 0; i

            map[i] = fileLines.get(i).toCharArray();

        }

        Mapmapping = new HashMap<>();

        MaprMapping = new HashMap<>();

        int counter = 0;

        int evens = 0;

        int odds = 0;

        for (int i = 0; i

            for (int j = 0; j

                if (map[i][j] == '#') {

                    counter++;

                    Location location = new Location(i, j);

                    mapping.put(location, counter);

                    rMapping.put(counter, location);

                    if (location.isEven()) {

                        evens++;

                    }

                    else {

                        odds++;

                    }

                }

            }

        }

        if (evens != odds) {

            result.add("impossible");

        }

        else {

            Edge[][] graph = new Edge[counter+2][counter+2];

            for (int i = 1; i<=counter; i++) {

                Location loc = rMapping.get(i);

                if (loc.isEven()) {

                    graph[0][i] = new Edge(0, i, 1);

                    graph[i][0] = new Edge(i, 0, 0);

                    Location upLocation = new Location(loc.row-1, loc.col);

                    if (mapping.containsKey(upLocation)) {

                        int index = mapping.get(upLocation);

                        graph[i][index] = new Edge(i, index, 1);

                        graph[index][i] = new Edge(index, i, 0);

                    }

                    Location downLocation = new Location(loc.row+1, loc.col);

                    if (mapping.containsKey(downLocation)) {

                        int index = mapping.get(downLocation);

                        graph[i][index] = new Edge(i, index, 1);

                        graph[index][i] = new Edge(index, i, 0);

                    }

                    Location leftLocation = new Location(loc.row, loc.col-1);

                    if (mapping.containsKey(leftLocation)) {

                        int index = mapping.get(leftLocation);

                        graph[i][index] = new Edge(i, index, 1);

                        graph[index][i] = new Edge(index, i, 0);

                    }

                    Location rightLocation = new Location(loc.row, loc.col+1);

                    if (mapping.containsKey(rightLocation)) {

                        int index = mapping.get(rightLocation);

                        graph[i][index] = new Edge(i, index, 1);

                        graph[index][i] = new Edge(index, i, 0);

                    }

                }

                else {

                    graph[counter+1][i] = new Edge(counter+1, i, 0);

                    graph[i][counter+1] = new Edge(i, counter+1, 1);

                }

            }

            Object[] flow = ff(graph, rMapping);

            int size = (int)flow[0];

            if (size == evens) {

                List edges = (List )flow[1];

                for (Edge e : edges) {

                    Location evenLoc = rMapping.get(e.from);

                    Location oddLoc = rMapping.get(e.to);

                    result.add(oddLoc.col + " " + oddLoc.row + " " + evenLoc.col + " " + evenLoc.row);

                }

            }

            else {

                result.add("impossible");

            }

        }

        return result;

    }

    private static class Location {

        int row;

        int col;

        Location(int row, int col) {

            this.row = row;

            this.col = col;

        }

        @Override

        public boolean equals(Object o) {

            if (this == o) return true;

            if (o == null || getClass() != o.getClass()) return false;

            Location location = (Location) o;

            return row == location.row && col == location.col;

        }

        @Override

        public int hashCode() {

            return Objects.hash(row, col);

        }

        public boolean isEven() {

            return (row + col) % 2 == 0;

        }

    }

}