import java.util.ArrayList;

public class Main {

    // Tablero, donde P = Pared, L = Libre, Q = Queso
    public static String[][] tablero = {{"P", "P", "P", "P", "P"},
                                        {"P", "L", "P", "L", "Q"},
                                        {"P", "L", "L", "L", "P"},
                                        {"L", "L", "P", "L", "L"},
                                        {"L", "L", "P", "L", "P"}};

    // Arreglo dinamico donde se guardan el historial de los movimientos realizados y exitosos
    public static ArrayList<Movimiento> historial = new ArrayList();

    public static void main(String[] args) {
        // Resolver el laberinto iniciando en la posicion (3,1)
        // En la recursion hay que ir pasando el historial para ir agregando los movimientos
        resolver(new Movimiento(3, 1), historial);

        // Imprime el historial de movimientos, que son los pasos para llevar a la meta
        for(int i=0; i<historial.size(); i++) {
            System.out.println("Paso " + (i+1) + ": " + historial.get(i).toString());
        }
    }

    // Donde se realiza el backtracking, donde recibe el siguiente movimiento y el historial de movimientos
    public static boolean resolver(Movimiento actual, ArrayList<Movimiento> historial) {
        // Caso de aceptacion
        if(gano(actual)) {
            historial.add(actual); // Agrega las coordenadas de la meta para quedar mas claro los pasos hasta llegar a la meta
            return true;
        }
        else {
            // Casos de rechazo
            // 1. Primero verifica que el movimiento nuevo no se encuentre en el historial de movimientos
            // 2. Luego verifica que el moviento sea valido, es decir que no llegue a una pared
            // 3. Como se verifica el OutOfBound, la generacion de movimientos puede retornar null entonces se valida que exista
            if(verificarMovimientoHistorial(actual) || verificarMovimientoValido(actual) || actual == null) {
                return false;
            }

            // Como el movimiento es valido se agrega al historial de movimientos
            historial.add(actual);

            // Llama al bactracking generando los nuevos movimientos, con una heuristica basica, es decir trata
            // de resolver de una esquina inferior izquierda a una esquina superior derecha
            // --------------
            // |        _ / |
            // |    _ /     |
            // |  /         |
            // --------------

            // Genera movimiento arriba, si el movimiento es valido sigue generando a partir de este nuevo movimiento
            if(resolver(generarMovimientoArriba(actual.getPosX(), actual.getPosY()), historial)) {
                return true;
            }

            // Genera movimiento derecha, si el movimiento es valido sigue generando a partir de este nuevo movimiento
            if(resolver(generarMovimientoDerecha(actual.getPosX(), actual.getPosY()), historial)) {
                return true;
            }

            // Genera movimiento izquierda, si el movimiento es valido sigue generando a partir de este nuevo movimiento
            if(resolver(generarMovimientoIzquierda(actual.getPosX(), actual.getPosY()), historial)) {
                return true;
            }

            // Genera movimiento abajo, si el movimiento es valido sigue generando a partir de este nuevo movimiento
            if(resolver(generarMovimientoAbajo(actual.getPosX(), actual.getPosY()), historial)) {
                return true;
            }

            // Si ninguno de los movimientos generados anteriormente ninguno es valido, se devuelve con el backtracking
            // y borra del historial de movimientos los movimientos invalidos ya que no llegan a la meta
            historial.remove(actual);
        }

        // Retorna false ya que con esta "ruta" no se llega a ninguna solucion y corta la rama del arbol y sigue con
        // la siguiente rama
        return false;
    }

    // Valida los limites de los indices
    public static boolean validarMovimientoIndice(int posX, int posY) {
        return (posX >= 0 && posX < tablero.length && posY >= 0 && posY < tablero.length);
    }

    // Generar los movimientos basicos de arriba, izquierda, derecha, abajo
    public static Movimiento generarMovimientoArriba(int posX, int posY) {
        if(validarMovimientoIndice(posX - 1, posY)) {
            return new Movimiento(posX - 1, posY);
        }

        return null;
    }

    public static Movimiento generarMovimientoAbajo(int posX, int posY) {
        if(validarMovimientoIndice(posX + 1, posY)) {
            return new Movimiento(posX + 1, posY);
        }

        return null;
    }

    public static Movimiento generarMovimientoIzquierda(int posX, int posY) {
        if(validarMovimientoIndice(posX, posY - 1)) {
            return new Movimiento(posX, posY - 1);
        }

        return null;
    }

    public static Movimiento generarMovimientoDerecha(int posX, int posY) {
        if(validarMovimientoIndice(posX, posY + 1)) {
            return new Movimiento(posX, posY + 1);
        }

        return null;
    }

    // Verificar si llego a la meta
    public static boolean gano(Movimiento actual) {
        boolean gano = false;

        if(tablero[actual.getPosX()][actual.getPosY()] == "Q") {
            gano = true;
        }

        return gano;
    }

    // Verificar que no choque con una pared
    public static boolean verificarMovimientoValido(Movimiento nuevo) {
        boolean valido = false;

        if(tablero[nuevo.getPosX()][nuevo.getPosY()] == "P") {
            valido = true;
        }

        return valido;
    }

    // Que ya pase por aqui, chequea el historial de movimientos
    public static boolean verificarMovimientoHistorial(Movimiento nuevo) {
        boolean existe = false;

        for(int i=0; i<historial.size(); i++) {
            if(historial.get(i).equals(nuevo)) {
                existe = true;
            }
        }

        return existe;
    }
}

public class Movimiento {

    private int posX;
    private int posY;

    public Movimiento(int posX, int posY) {
        this.posX = posX;
        this.posY = posY;
    }

    public int getPosX() {
        return posX;
    }

    public void setPosX(int pos) {
        this.posX = pos;
    }

    public int getPosY() {
        return posY;
    }

    public void setPosY(int posY) {
        this.posY = posY;
    }

    @Override
    public boolean equals(Object obj) {
        Movimiento m = (Movimiento) obj;

        if(this.getPosX() == m.getPosX() && this.getPosY() == m.getPosY()) {
            return true;
        }
        else {
            return false;
        }
    }

    @Override
    public String toString() {
        return "X: " + this.getPosX() + " - " + "Y: " + this.getPosY();
    }
}