[ADSx] - Fixed Graph Codes

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Board {

    public static void main(String args[]) {
        String text = "100 100\n" +
                "2 100 50 50";
        //text = "3 3\n" +
        //       "1 1 3 3";

        //text = "8 8 \n" +
        //        "1 1 8 8";
        Scanner scanner = new Scanner(text);
        //Scanner scanner = new Scanner(System.in);
        int rows = scanner.nextInt();
        int columns = scanner.nextInt();
        scanner.nextLine();

        // Minus one for all because we iterate starting from 0
        int x1 = scanner.nextInt() - 1;
        int y1 = scanner.nextInt() - 1;
        int x2 = scanner.nextInt() - 1;
        int y2 = scanner.nextInt() - 1;

        /**
         * https://en.wikipedia.org/wiki/Knight%27s_graph
         * https://www.geeksforgeeks.org/minimum-steps-reach-target-knight/
         * */

        Integer elements[] = new Integer[(rows + 1) * (columns + 1)];
        IntStream.range(0, elements.length).forEach(i -> elements[i] = i);

        //System.out.print(Arrays.toString(elements));

        Graph<Integer> graph = new Graph<>((rows + 1) * (columns + 1), elements);

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (i + 2 < rows && j + 1 < columns) {
                    graph.addEdge(transform(i, j, columns), transform(i + 2, j + 1, columns), 1);
                }
                if (i + 2 < rows && j - 1 >= 0) {
                    graph.addEdge(transform(i, j, columns), transform(i + 2, j - 1, columns), 1);
                }
                if (i - 2 >= 0 && j + 1 < columns) {
                    graph.addEdge(transform(i, j, columns), transform(i - 2, j + 1, columns), 1);
                }
                if (i - 2 >= 0 && j - 1 >= 0) {
                    graph.addEdge(transform(i, j, columns), transform(i - 2, j - 1, columns), 1);
                }
                if (j + 2 < columns && i + 1 < rows) {
                    graph.addEdge(transform(i, j, columns), transform(j + 2, i + 1, columns), 1);
                }
                if (j + 2 < columns && i - 1 >= 0) {
                    graph.addEdge(transform(i, j, columns), transform(j + 2, i - 1, columns), 1);
                }
                if (j - 2 >= 0 && i + 1 < rows) {
                    graph.addEdge(transform(i, j, columns), transform(j - 2, i + 1, columns), 1);
                }
                if (j - 2 >= 0 && i - 1 >= 0) {
                    graph.addEdge(transform(i, j, columns), transform(j - 2, i - 1, columns), 1);
                }
            }
        }

        int from = transform(x1, y1, columns);
        int to = transform(x2, y2, columns);
        //int steps = bfsSearch(graph, from, to);

        System.out.println(graph.dijkstra(from, to));

    }

    public static int transform(int i, int j, int n) {
        return i * n + j;
    }
/*
    public static int bfsSearch(Graph<Integer> g, int from, int to) {
        Queue<Integer> nodes = new LinkedList<>();
        Queue<Integer> steps = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        nodes.add(from);
        steps.add(0);
        while (!nodes.isEmpty()) {
            int c = nodes.poll();
            int st = steps.poll();
            if (visited.contains(c)) {
                continue;
            }
            visited.add(c);
            if (c == to) {
                return st;
            }
            GraphNode<Integer> current = g.adjList[c];
            for (GraphNode<Integer> neighbor : current.getNeighbors()) {
                nodes.add(neighbor.getIndex());
                steps.add(st + 1);
            }
        }
        return -1;
    }

    public static <T> void printMatrix(T matrix[][]) {
        System.out.println("Main.");
        Arrays.stream(matrix)
                .map(Arrays::toString)
                .forEach(System.out::println);
    }

    public static boolean isInside(int x, int y, int N) {
        if (x >= 1 && x <= N && y >= 1 && y <= N) return true;
        return false;
    }

    public static int minStepToReachTarget(int knightPos[], int targetPos[], int N) {
        //  x and y direction, where a knight can move
        int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
        int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};

        //  queue for storing states of knight in board
        Queue<Cell> queue = new LinkedList<>();

        //  push starting position of knight with 0 distance
        queue.add(new Cell(knightPos[0], knightPos[1], 0));

        Cell t;
        int x, y;
        boolean visited[][] = new boolean[N + 1][N + 1];

        //  make all cell unvisited
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                visited[i][j] = false;

        //  visit starting state
        visited[knightPos[0]][knightPos[1]] = true;

        //  loop until we have one element in queue
        while (!queue.isEmpty()) {
            t = queue.poll();
            visited[t.x][t.y] = true;

            // if current cell is equal to target cell,
            // return its distance
            if (t.x == targetPos[0] && t.y == targetPos[1])
                return t.dis;

            //  loop for all reachable states
            for (int i = 0; i < dx.length; i++) {
                x = t.x + dx[i];
                y = t.y + dy[i];

                // If rechable state is not yet visited and
                // inside board, push that state into queue
                if (isInside(x, y, N) && !visited[x][y])
                    queue.add(new Cell(x, y, t.dis + 1));

            }
        }
        return -1;
    }

*/
}


class Edge implements Comparable<Edge> {
    // Private
    private int fromVertex, toVertex;
    private int weight;

    // Public
    public Edge(int from, int to, int weight) {
        this.fromVertex = from;
        this.toVertex = to;
        this.weight = weight;
    }

    public int getFrom() {
        return this.fromVertex;
    }

    public int getTo() {
        return this.toVertex;
    }

    public int getWeight() {
        return this.weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(weight, o.weight);
    }
}

class GraphNode<E> {
    // Private
    private int index;
    private E info;
    private LinkedList<GraphNodeNeighbor<E>> neighbors;

    // Public
    public GraphNode(int index, E info) {
        this.index = index;
        this.info = info;
        neighbors = new LinkedList<>();
    }

    public boolean containsNeighbor(GraphNode<E> o) {
        return neighbors.contains(new GraphNodeNeighbor<>(o));
    }

    public void addNeighbor(GraphNode<E> o, int weight) {
        neighbors.add(new GraphNodeNeighbor<>(o, weight));
    }

    public void removeNeighbor(GraphNode<E> o) {
        neighbors.remove(new GraphNodeNeighbor<>(o));
    }

    @Override
    public String toString() {
        return neighbors.stream().map(i -> "(" + i.node.index + "," + i.weight + ")").collect(Collectors.joining(" ", "INFO:" + index + " SOSEDI:", ""));
    }

    public void updateNeighborWeight(GraphNode<E> o, int weight) {
        for (GraphNodeNeighbor<E> pom : neighbors)
            if (pom.node.equals(o))
                pom.weight = weight;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;

        GraphNode<?> graphNode = (GraphNode<?>) o;

        return index == graphNode.index;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public E getInfo() {
        return info;
    }

    public void setInfo(E info) {
        this.info = info;
    }

    public LinkedList<GraphNodeNeighbor<E>> getNeighbors() {
        return neighbors;
    }

    public void setNeighbors(LinkedList<GraphNodeNeighbor<E>> neighbors) {
        this.neighbors = neighbors;
    }
}

class GraphNodeNeighbor<E> {
    // Private
    GraphNode<E> node;
    int weight;

    // Public
    public GraphNodeNeighbor(GraphNode<E> node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    public GraphNodeNeighbor(GraphNode<E> node) {
        this.node = node;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;

        GraphNodeNeighbor<?> that = (GraphNodeNeighbor<?>) o;

        return node != null ? node.equals(that.node) : that.node == null;
    }
}

class Graph<E> {
    // Private
    private int nodesCount;
    private GraphNode<E>[] adjacencyList;

    // Public
    public Graph(int nodesCount, E[] list) {
        this.nodesCount = nodesCount;
        adjacencyList = (GraphNode<E>[]) new GraphNode[nodesCount];
        for (int i = 0; i < nodesCount; i++)
            adjacencyList[i] = new GraphNode<>(i, list[i]);
    }

    public Graph(int nodesCount) {
        this.nodesCount = nodesCount;
        adjacencyList = (GraphNode<E>[]) new GraphNode[nodesCount];
        for (int i = 0; i < nodesCount; i++)
            adjacencyList[i] = new GraphNode<>(i, null);
    }

    int adjacent(int node1index, int node2index) {
        return adjacencyList[node1index].containsNeighbor(adjacencyList[node2index]) ? 1 : 0;
    }

    void addEdge(int node1index, int node2index, int weight) {
        if (adjacencyList[node1index].containsNeighbor(adjacencyList[node2index]))
            adjacencyList[node1index].updateNeighborWeight(adjacencyList[node2index], weight);
        else
            adjacencyList[node1index].addNeighbor(adjacencyList[node2index], weight);
    }

    void deleteEdge(int node1index, int node2index) {
        adjacencyList[node1index].removeNeighbor(adjacencyList[node2index]);
    }

    public void setAdjacencyListAt(int index, E x) {
        adjacencyList[index].setInfo(x);
    }

    public GraphNode<E>[] getAdjacencyList() {
        return adjacencyList;
    }

    /*************************** KRUSKAL ***********************************************************************/
    public Edge[] getAllEdges() {
        int totalEdges = Arrays.stream(adjacencyList).mapToInt(i -> i.getNeighbors().size()).sum();
        Edge[] edges = new Edge[totalEdges];
        int index = 0;
        for (GraphNode<E> node : adjacencyList)
            for (GraphNodeNeighbor<E> neighbor : node.getNeighbors()) {
                int index1 = node.getIndex();
                int index2 = neighbor.node.getIndex();
                int weight = neighbor.weight;
                edges[index++] = new Edge(index1, index2, weight);
            }
        return edges;
    }

    private int[] union(int u, int v, int[] links) {
        int findWhat = links[u < v ? v : u];
        int replaceWith = links[u < v ? u : v];
        IntStream.range(0, links.length).filter(i -> links[i] == findWhat).forEach(i -> links[i] = replaceWith);
        return links;
    }

    public List<Edge> kruskal() {
        int[] links = new int[this.nodesCount];
        Edge[] edges = this.getAllEdges();
        Arrays.sort(edges);
        Arrays.setAll(links, i -> i);
        List<Edge> mstEdges = new ArrayList<>();
        for (Edge e : edges) {
            if (links[e.getFrom()] != links[e.getTo()]) {
                mstEdges.add(e);
                links = this.union(e.getFrom(), e.getTo(), links);
            }
            if (mstEdges.size() == (this.nodesCount - 1))
                break;
        }
        return mstEdges;
    }

    /*******************************************************************************************************/
    /************************ PRIM **************************************************************************/

    private Edge getMinimalEdge(boolean[] included) {
        int index1 = Integer.MAX_VALUE, index2 = Integer.MAX_VALUE;
        int minweight = Integer.MAX_VALUE;
        Double myMin = Arrays.stream(adjacencyList).filter(i -> included[i.getIndex()]).flatMapToDouble(adl -> adl.getNeighbors().stream().filter(i -> !included[i.node.getIndex()]).mapToDouble(n -> n.weight)).min().orElse(0);
        for (int i = 0; i < this.nodesCount; i++) {
            if (included[i]) {
                for (GraphNodeNeighbor<E> pom : adjacencyList[i].getNeighbors()) {
                    if (!included[pom.node.getIndex()] && pom.weight < minweight) {
                        index1 = i;
                        index2 = pom.node.getIndex();
                        minweight = pom.weight;
                    }
                }
            }
        }
        int breakHere = 1;
        System.out.println("###################");
        System.out.printf("myMin %f minweight %f\n", myMin, minweight);
        System.out.println(myMin == minweight);
        System.out.println("###################");
        return minweight < Integer.MAX_VALUE ? new Edge(index1, index2, minweight) : null;
    }

    public List<Edge> prim(int start_index) {
        List<Edge> mstEdges = new ArrayList<>();
        boolean[] included = new boolean[this.nodesCount];
        Arrays.fill(included, false);
        included[start_index] = true;
        for (int i = 0; i < this.nodesCount - 1; i++) {
            Edge e = this.getMinimalEdge(included);
            if (e == null) {
                System.out.println("Ne mozat da se povrzat site jazli");
                break;
            }
            included[e.getFrom()] = included[e.getTo()] = true;
            mstEdges.add(e);
        }
        return mstEdges;
    }

    /*******************************************************************************************************/
    /***************** DIJKSTRA ******************************************************************************/

    public int dijkstra(int from, int to) {
        int[] distance = new int[this.nodesCount];
        boolean[] finalno = new boolean[this.nodesCount];
        Arrays.fill(distance, -1);
        Arrays.fill(finalno, false);
        finalno[from] = true;
        distance[from] = 0;
        for (int i = 1; i < this.nodesCount; i++) {
            for (GraphNodeNeighbor<E> pom : adjacencyList[from].getNeighbors()) {
                if (!finalno[pom.node.getIndex()]) {
                    if (distance[pom.node.getIndex()] <= 0) {
                        distance[pom.node.getIndex()] = distance[from] + pom.weight;
                    } else if (distance[from] + pom.weight < distance[pom.node.getIndex()]) {
                        distance[pom.node.getIndex()] = distance[from] + pom.weight;
                    }
                }
            }
            boolean minit = false;
            int k = 0;
            int minc = -1;
            for (int j = 0; j < this.nodesCount; j++) {
                if (!finalno[j] && distance[j] != -1) {
                    if (!minit) {
                        minc = distance[k = j];
                        minit = true;
                    } else if (minc > distance[j] && distance[j] > 0)
                        minc = distance[k = j];
                }
            }
            finalno[from = k] = true;
        }
        return distance[to];
    }

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

    @Override
    public String toString() {
        return Arrays.stream(adjacencyList).map(GraphNode::toString).collect(Collectors.joining("\n"));
    }
}

class Cell {
    Integer x;
    Integer y;
    Integer dis;

    public Cell(Integer x, Integer y, Integer dis) {
        this.x = x;
        this.y = y;
        this.dis = dis;
    }
}

/**
 * Дадена е една шаховска табла mxn и на неа е даден една шаховска фигура - коњ поставен во некое поле (x,y) на таблата. Коњот на шаховската табла легално во еден потег може да се движи или за две позиции вертикално и една хоризонтално или за две позиции хоризонтално и една вертикално, т.е. од позиција (x,y) може да се движи на една од следните позиции (x±1,y±2) или (x±2,y±1) (види слика). Да се најде минималниот број на потези за коњот да се придвижи од едно дадено почетно поле до едно дадено крајно поле на таблата.
 * <p>
 * enter image description here
 * <p>
 * Влез: Во првиот ред од влезот се дадени бројот на редици и колони на таблата (5<=m,n<=100), а во вториот ред се дадени полињата на почетокот и крајот на движењето на коњот (x1,y1) и (x2,y2) .
 * <p>
 * Излез: Да се испечати минималниот број на потези за коњот да се придвижи од едно дадено почетно поле до едно дадено крајно поле на таблата.
 * <p>
 * Делумно решение: Задачата се смета за делумно решена доколку се поминати 4 тест примери.
 * <p>
 * Пример:
 * <p>
 * Влез:
 * <p>
 * 5 5
 * <p>
 * 1 2 4 3
 * <p>
 * Излез:
 * <p>
 * 2
 * <p>
 * За да коњот се придвижи од позиција (1,2) до позиција (4,3) на шаховска табла 5x5 потребни се минимум 2 потега.
 * <p>
 * Име на класа (Јава): Board
 */