chess_knight.java

package chess;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Graph {
    final Set<Node> nodes;
    final Set<Edge> edges;
    final Map<Node, Set<Edge>> edgesPerNode;

    Graph(Set<Node> nodes, Set<Edge> edges) {
        this.nodes = nodes;
        this.edges = edges;
        edgesPerNode = new HashMap<>();
        for (Node node : nodes) {
            edgesPerNode.put(node, new HashSet<>());
        }
        for (Edge edge : edges) {
            edgesPerNode.get(edge.a).add(edge);
        }
    }
}

class Node {
    final int x, y;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

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

        Node node = (Node) o;

        return x == node.x && y == node.y;

    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }
}

class Edge {
    final Node a, b;

    Edge(Node a, Node b) {
        this.a = a;
        this.b = b;
    }

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

        Edge edge = (Edge) o;

        return a != null ? a.equals(edge.a) : edge.a == null && (b != null ? b.equals(edge.b) : edge.b == null);

    }

    @Override
    public int hashCode() {
        int result = a != null ? a.hashCode() : 0;
        result = 31 * result + (b != null ? b.hashCode() : 0);
        return result;
    }
}

package chess;

import java.awt.*;
import java.util.*;

public class Chess {

    static Graph toKnightGraph(int[][] board) {
        Set<Node> nodes = new HashSet<>(board.length * board.length);
        Set<Node> restrictedNodes = new HashSet<>();
        Set<Edge> edges = new HashSet<>(board.length * board.length * 8);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                Node node = new Node(i, j);
                nodes.add(node);

                if (board[i][j] == 1) {
                    restrictedNodes.add(node);
                }
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                addEdgesForNode(new Node(i, j), board.length, edges, restrictedNodes);
            }
        }

        return new Graph(nodes, edges);
    }

    static class IntRef {
        int i;
    }

    static int distance(Graph graph, Node a, Node b) {
        Map<Node, Integer> distances = new HashMap<>();
        Map<Node, Color> colors = new HashMap<>();
        IntRef time = new IntRef();
        for (Node node : graph.nodes) {
            distances.put(node, -1);
            colors.put(node, Color.WHITE);
        }

        for (Node node : graph.nodes) {
            if (colors.get(node) == Color.WHITE) {
                dfsVisit(node, distances, colors, time, graph.edgesPerNode);
            }
        }
        return distances.get(b);
    }

    private static void dfsVisit(Node node,
                                 Map<Node, Integer> distances,
                                 Map<Node, Color> colors,
                                 IntRef time,
                                 Map<Node, Set<Edge>> edges) {
        colors.put(node, Color.GRAY);
        time.i++;
        distances.put(node, time.i);
        for (Edge edge : edges.get(node)) {
            if (colors.get(edge.b) == Color.WHITE) {
                dfsVisit(edge.b, distances, colors, time, edges);
            }
        }
        colors.put(node, Color.BLACK);
        time.i++;
    }


    private static void addEdgesForNode(Node node, int sideLength, Set<Edge> edges,
                                        Set<Node> restrictedNodes) {
        int x = node.x, y = node.y;
        int[] otherX = new int[]{x + 1, x + 2, x + 2, x + 1,
                x - 1, x - 2, x - 2, x - 1};
        int[] otherY = new int[]{y + 2, y + 1, y - 1, y - 2,
                y - 2, y - 1, y + 1, y + 2};

        for (int i = 0; i < otherX.length; i++) {
            int newX = otherX[i];
            int newY = otherY[i];
            Node otherNode = new Node(newX, newY);

            if (newX < sideLength && newY < sideLength && newX >= 0 && newY >= 0
                    && !restrictedNodes.contains(otherNode)) {
                edges.add(new Edge(node, otherNode));
            }
        }
    }

    public static void main(String... args) {
        int[][] board;

        Graph g = toKnightGraph(board);
        int distance = distance(g, new Node(startX, startY), new Node(targetX, targetY));
        System.out.println(distance);
    }
}