Soluzione Labirinto

public class Labirinto {
 
    //rappresentazione dell'informazione
 
    private boolean parete[][];
    private boolean marca[][];
    private int percorso[][];
    private int n; //dimensione del labirinto
 
    //costruttore
    public Labirinto(int dimens) {
        n=dimens;
        parete = new boolean[n][n];
        int i, j;
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                parete[i][j]=false;
    }
 
    //metodi pubblici richiesti
    public void impostaParete(int i, int j) {
        parete[i][j]=true;
    }
 
    public boolean risolviLabirinto(int is, int js, int id, int jd) {
        //creo e inizializzo gli array marca e percorso
        marca = new boolean[n][n];
        percorso = new int[n][n];
        int i, j;
        for(i=0; i<n; i++)
            for(j=0; j<n; j++) {
                marca[i][j]=false;
                percorso[i][j]=0;
            }
 
        //invoco il metodo ricorsivo e restituisco il risultato
        return risolviLabirintoRic(is, js, id, jd, 1);
    }
 
    public int dammiPosizioneNelPercorso(int i, int j) {
        return percorso[i][j];
    }
 
    //metodo ricorsivo
 
    boolean risolviLabirintoRic(int i, int j, int id, int jd, int k) {
 
        //Se non siamo su una stanza: es. parete o fuori dal labirinto
        if(i<0 || i>=n || j<0 || j>=n || parete[i][j])
            return false;
 
        //Se la cella attuale è già marcata, non la visitiamo di nuovo
        if(marca[i][j]) 
            return false;
 
        marca[i][j] = true;
 
        //toglieremo questa marcatura se dovremo restituire false:
        percorso[i][j]=k; 
 
        //Caso base: destinazione raggiunta
        if(i==id && j==jd)
            return true;
 
        //Per ogni cella adiacente: (iAd, jAd) in {(i, j-1), (i, j+1), (i-1, j), (i+1, j)}
        //invocare il metodo risolviLabirintoRicorsivo(iAd, jAd, id, jd, k+1).
        //Appena una invocazione restituisce true,
        //restituire true:          
        if(
            risolviLabirintoRic(i+1, j, id, jd, k+1)
            || risolviLabirintoRic(i-1, j, id, jd, k+1)
            || risolviLabirintoRic(i, j+1, id, jd, k+1)
            || risolviLabirintoRic(i, j-1, id, jd, k+1)
        )
            return true;
 
 
        //Altrimenti:
        //non abbiamo trovato il percorso perché non esiste
 
        //Togliamo la marcatura come parte del percorso
        percorso[i][j]=0;
 
        return false;
 
    }
 
    //Metodo main richiesto per il test
    public static void main(String[] args) {
 
        final int n=5;
 
        //creo il labirinto
        Labirinto l=new Labirinto(n);
 
        l.impostaParete(1, 0);
        l.impostaParete(1, 1);
        l.impostaParete(1, 2);
        l.impostaParete(1, 3);
        l.impostaParete(3, 1);
        l.impostaParete(3, 2);
        l.impostaParete(3, 3);
        l.impostaParete(3, 4);
 
        l.risolviLabirinto(0, 0, 4, 4);
 
        //Stampa risultato
        int i, j;
        for(j=0; j<n; j++) { //Stampo per righe
            for(i=0; i<n; i++) {
                System.out.printf("%2d", l.dammiPosizioneNelPercorso(i, j));
                if(i < n-1)
                    System.out.print(", ");
                else
                    System.out.println("");
            } 
        }
 
 
    }
 
 
}