import java.util.*;

class Labyrint {

    private final char[][] lab = {
        { '.', '.', '.', '.', 'X' },
        { '.', 'X', 'X', '.', 'X' },
        { '.', 'X', 'X', '.', 'X' },
        { '.', '.', '.', '.', '.' },
    };
    private final int[] inngang = { 0, 1 };
    private final int[] utgang = { 3, 4 };

    private static final int[][] RETNINGER = {
        { -1, 0 },
        { 0, 1 },
        { 1, 0 },
        { 0, -1 },
    };

    private final int antallRader;
    private final int antallKolonner;

    public Labyrint() {
        antallRader = lab.length;
        antallKolonner = lab[0].length;
    }

    public List<List<int[]>> finnAlle() {
        List<List<int[]>> alleRuter = new ArrayList<>();
        boolean[][] bes?kt = new boolean[antallRader][antallKolonner];
        List<int[]> aktuellRute = new ArrayList<>();
        finnR(inngang, bes?kt, aktuellRute, alleRuter);
        return alleRuter;
    }

    private void finnR(
        int[] pos,
        boolean[][] bes?kt,
        List<int[]> aktuellRute,
        List<List<int[]>> alleRuter
    ) {
        int rad = pos[0];
        int kol = pos[1];
        // base 1, utenfor
        if (rad < 0 || rad >= antallRader || kol < 0 || kol >= antallKolonner) {
            return;
        }

        // base 2, vegg
        if (lab[rad][kol] == 'X') {
            return;
        }

        // base 3, bes?kt (for unng? sykler)
        if (bes?kt[rad][kol]) {
            return;
        }

        aktuellRute.add(pos);
        bes?kt[rad][kol] = true;

        // base 4 utgang
        if (Arrays.equals(pos, utgang)) {
            alleRuter.add(new ArrayList<>(aktuellRute));
            aktuellRute.remove(aktuellRute.size() - 1);
            bes?kt[rad][kol] = false;
            return;
        }

        // rekursivt hver retning
        for (int[] retning : RETNINGER) {
            int[] nestePos = { rad + retning[0], kol + retning[1] };
            finnR(nestePos, bes?kt, aktuellRute, alleRuter);
        }

        // backtrack
        aktuellRute.remove(aktuellRute.size() - 1);
        bes?kt[rad][kol] = false;
    }

    public void skrivUt(List<int[]> rute) {
        char[][] kopi = new char[antallRader][antallKolonner];
        for (int i = 0; i < antallRader; i++) {
            kopi[i] = Arrays.copyOf(lab[i], antallKolonner);
        }

        if (rute != null && !rute.isEmpty()) {
            for (int i = 1; i < rute.size() - 1; i++) {
                int[] p = rute.get(i);
                kopi[p[0]][p[1]] = '+';
            }
        } else {
            System.out.println(
                String.format(
                    "Inngang (%d,%d), utgang (%d,%d)",
                    inngang[0] + 1,
                    inngang[1] + 1,
                    utgang[0] + 1,
                    utgang[1] + 1
                )
            );
        }

        for (int r = 0; r < antallRader; r++) {
            for (int k = 0; k < antallKolonner; k++) {
                if (inngang[0] == r && inngang[1] == k) {
                    System.out.print("I");
                } else if (utgang[0] == r && utgang[1] == k) {
                    System.out.print("U");
                } else {
                    System.out.print(kopi[r][k]);
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Labyrint labyrint = new Labyrint();

        System.out.println("Labyrint:");
        labyrint.skrivUt(null);

        List<List<int[]>> ruter = labyrint.finnAlle();

        if (ruter.isEmpty()) {
            System.out.println("Ingen ruter funnet.");
        } else {
            System.out.println(
                "Fant " + ruter.size() + " rute" + (ruter.size() > 1 ? "r" : "")
            );
            for (List<int[]> ruten : ruter) {
                System.out.println("Rute:");
                for (int[] pos : ruten) {
                    System.out.print(
                        String.format("(%d,%d) ", pos[0] + 1, pos[1] + 1)
                    );
                }
                System.out.println();
                labyrint.skrivUt(ruten);
            }
        }
    }
}