import java.util.*;

class Skattejakt {

    private static final String LAND = "?";
    private static final String VANN = "\u001B[34m¨€\u001B[0m";
    private static final String SKATT = "?";
    private static final String STI = "?";
    private static final String PIRAT = "?";

    private static String[][] kart;
    private static int st?rrelse;
    private static int skattX, skattY;
    private static List<int[]> stier = new ArrayList<>();
    private static Random random = new Random();

    public static void main(String[] args) {
        st?rrelse = args.length > 0 ? Integer.parseInt(args[0]) : 10;
        kart = new String[st?rrelse][st?rrelse];
        lagKart();
        int startX = random.nextInt(st?rrelse);
        int startY = random.nextInt(st?rrelse);
        visKart(startX, startY);
        boolean funnet = finnStiTilSkatt(
            startX,
            startY,
            new boolean[st?rrelse][st?rrelse]
        );
        if (funnet) {
            System.out.println("Funnet skatten!");
            visSti(stier, 0);
        } else {
            System.out.println("Fant ikke skatten!");
        }
    }

    public static void lagKart() {
        for (int i = 0; i < st?rrelse; i++) {
            for (int j = 0; j < st?rrelse; j++) {
                double sentrum =
                    Math.abs(i - st?rrelse / 2.0) +
                    Math.abs(j - st?rrelse / 2.0);
                kart[i][j] = random.nextDouble() < (sentrum / st?rrelse)
                    ? VANN
                    : LAND;
            }
        }
        skattX = random.nextInt(st?rrelse - 4) + 2;
        skattY = random.nextInt(st?rrelse - 4) + 2;
        kart[skattX][skattY] = SKATT;
    }

    private static void visKart(int piratX, int piratY) {
        for (int i = 0; i < st?rrelse; i++) {
            for (int j = 0; j < st?rrelse; j++) {
                if (i == piratX && j == piratY) {
                    System.out.print(PIRAT);
                } else if (kart[i][j].equals(LAND)) {
                    System.out.print(LAND);
                } else if (kart[i][j].equals(VANN)) {
                    System.out.print(VANN);
                } else if (kart[i][j].equals(SKATT)) {
                    System.out.print(SKATT);
                } else {
                    System.out.print(kart[i][j]);
                }
            }
            System.out.println();
        }
    }

    private static boolean finnStiTilSkatt(int x, int y, boolean[][] bes?kt) {
        // base case
        if (
            x < 0 || x >= st?rrelse || y < 0 || y >= st?rrelse || bes?kt[x][y]
        ) {
            return false;
        }
        if (kart[x][y].equals(SKATT)) {
            stier.add(new int[] { x, y });
            return true;
        }
        bes?kt[x][y] = true;
        int[][] retninger = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
        for (int[] retning : retninger) {
            int nyX = x + retning[0];
            int nyY = y + retning[1];
            if (finnStiTilSkatt(nyX, nyY, bes?kt)) {
                stier.add(0, new int[] { x, y });
                return true;
            }
        }
        return false;
    }

    private static void visSti(List<int[]> sti, int skritt) {
        if (skritt >= sti.size()) return;
        System.out.print("\033[H\033[2J"); // blank skjerm

        int piratX = sti.get(skritt)[0];
        int piratY = sti.get(skritt)[1];
        visKart(piratX, piratY);
        kart[piratX][piratY] = STI;
        long forsinkelse = kart[piratX][piratY].equals(VANN) ? 100 : 500;
        try {
            Thread.sleep(forsinkelse);
        } catch (InterruptedException e) {}
        visSti(sti, skritt + 1);
    }
}