/**
 * Created by Ilya Gazman on 10/17/2018.
 */
public class BFS {

    private static final boolean DEBUG = false;

    public ArrayList<Point> findPath(int[][] map, Point position, Point destination) {
        if (isOutOfMap(map, position)) {
            return null;
        }
        if (isOutOfMap(map, destination)) {
            return null;
        }
        if (isBlocked(map, position)) {
            return null;
        }
        if (isBlocked(map, destination)) {
            return null;
        }
        LinkedList<Point> queue1 = new LinkedList<>();
        LinkedList<Point> queue2 = new LinkedList<>();

        queue1.add(position);
        int stepCount = 1;
        while (!queue1.isEmpty()) {
            for (Point point : queue1) {
                map[point.y][point.x] = -stepCount;
            }

            for (Point point : queue1) {
                if (point.x == destination.x && point.y == destination.y) {
                    ArrayList<Point> optimalPath = new ArrayList<>();
                    computeSolution(map, point.x, point.y, stepCount, optimalPath);
                    resetMap(map);
                    return optimalPath;
                }
                LinkedList<Point> finalQueue = queue2;
                lookAround(map, point, (x, y) -> {
                    if (isBlocked(map, x, y)) {
                        return;
                    }
                    finalQueue.add(new Point(x, y));
                });
            }

            if (DEBUG) {
                printMap(map);
            }

            queue1 = queue2;
            queue2 = new LinkedList<>();
            stepCount++;
        }
        resetMap(map);
        return null;
    }

    private void resetMap(int[][] map) {
        for (int y = 0; y < map.length; y++) {
            for (int x = 0; x < map[0].length; x++) {
                if (map[y][x] < 0) {
                    map[y][x] = 0;
                }
            }
        }
    }

    private boolean isBlocked(int[][] map, Point p) {
        return isBlocked(map, p.x, p.y);
    }

    private boolean isBlocked(int[][] map, int x, int y) {
        int i = map[y][x];
        return i < 0 || i == 1;
    }

    private void printMap(int[][] map) {
        for (int y = 0; y < map[0].length; y++) {
            for (int x = 0; x < map.length; x++) {
                System.out.print(map[y][x] + "t");
            }
            System.out.println();
        }
        System.out.println("****************************************");
    }

    private void computeSolution(int[][] map, int x, int y, int stepCount, ArrayList<Point> optimalPath) {
        if (isOutOfMap(map, x, y)) {
            return;
        }

        if (optimalPath.size() - stepCount != map[y][x]) {
            return;
        }

        Point p = new Point(x, y);
        optimalPath.add(p);
        lookAround(map, p, (x1, y1) -> computeSolution(map, x1, y1, stepCount, optimalPath));
    }

    private void lookAround(int[][] map, Point p, Callback callback) {
        callback.look(map, p.x + 1, p.y);
        callback.look(map, p.x - 1, p.y);
        callback.look(map, p.x, p.y + 1);
        callback.look(map, p.x, p.y - 1);
        callback.look(map, p.x + 1, p.y + 1);
        callback.look(map, p.x - 1, p.y + 1);
        callback.look(map, p.x - 1, p.y - 1);
        callback.look(map, p.x + 1, p.y - 1);
    }

    private static boolean isOutOfMap(int[][] map, Point p) {
        return isOutOfMap(map, p.x, p.y);
    }

    private static boolean isOutOfMap(int[][] map, int x, int y) {
        if (x < 0 || y < 0) {
            return true;
        }
        return map.length == y || map[0].length == x;
    }

    private interface Callback {
        default void look(int[][] map, int x, int y) {
            if (isOutOfMap(map, x, y)) {
                return;
            }
            onLook(x, y);
        }

        void onLook(int x, int y);
    }
}