Java 2D Array, Rekursion

[hubertus1990]

Ich hab ein zweidimensionales boolean array, von dem ich rekursiv berechnen möchte, ob es einen gültigen Pfad von array[0][0] bis array[max][max] gibt.

Ein Pfad ist gültig wenn die werte "true" sind. Es werden immer die diagonalen und horizontalen Nachbarn auf "true" überprüft. Sind Sie "true", so geht der Pfad weiter.
Dazu ein kleines Beispiel:

0 = false, 1 = true

Gültiger Pfad von [0][0] bis [4][4]:

    1 1 0 0 0
    0 1 0 0 0
    1 1 0 0 0
    1 0 0 0 0
    1 1 1 1 1

Ungültiger Pfad:

    1 1 0 0 0
    0 1 0 0 0
    1 0 0 0 0
    1 0 0 0 0
    1 1 1 1 1

Diagonale Nachbarn zählen nicht.

Ich habe den Algorithmus auch schon soweit fertig implementiert, und die Ausgabe passt perfekt, allerdings stimmt der return value nicht immer. Mir ist nicht genau klar wo ich "was" returnen soll.

Hier mein Code:

static boolean isValidPath(boolean [][] field, int i, int j, int previ, int prevj) {
    		
    	if(i >= field.length && j >= field[0].length) return true;
    		
    		
    	if(field[i][j] == true) {
    			
    	System.out.println("Valid i: " + i + ", j: " + j);
    	if(i + 1 < field.length && i + 1 != previ) isValidPath(field, i + 1, j, i, j);
    	if(j + 1 < field[0].length && j + 1 != prevj) isValidPath(field, i, j + 1, i, j);
    	if(i - 1 >= 0 && i - 1 != previ) isValidPath(field, i - 1, j, i, j);
    	if(j - 1 >= 0 && j - 1 != prevj) isValidPath(field, i, j - 1, i, j);
    			
    	return true;
    			
    } else return false;
}
    	
public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    boolean[][] field = new boolean[][] { 
     { true,  true, false, false, false}, 
     { false, true, false, false, false},
     { true,  true, false, false, false},
     { true, false, false, false, false}, 
     { true, true, true, true, true }};
    		
    	System.out.println("Is this path valid: " + isValidPath(field, 0, 0, 0, 0));
}

Und hier die Ausgabe dazu:

Valid i: 0, j: 0
Valid i: 0, j: 1
Valid i: 1, j: 1
Valid i: 2, j: 1
Valid i: 2, j: 0
Valid i: 3, j: 0
Valid i: 4, j: 0
Valid i: 4, j: 1
Valid i: 4, j: 2
Valid i: 4, j: 3
Valid i: 4, j: 4
Is this path valid: true

Wie man sieht entspricht die Ausgabe genau dem Pfad. Allerdings ist zB. der return Wert auch "true", wenn ich den wert in field[4][4] auf "false" setze.

 

[R3ddy]

Wenn ich es richtig sehe muss "true" zurückgegeben werden, falls ein rekursiver Aufruf "true" zurückgibt. Falls bei allen Aufrufen dies nicht der Fall ist, gibst du stattdessen "false" zurück.

Bei deinem Code existiert allerdings das Problem, dass falls ein geschlossener Weg innerhalb des Feldes existiert (zum Beispiel ein 2x2 großes Quadrat mit "true" Werten) es zu einer Endlosschleife kommt.

Edit:
Außerdem scheint es mir so, dass deine Abbruchbedingung nicht ganz korrekt ist. Diese sollte sein, dass deine Zielposition erreicht ist.

 

[hubertus1990]

Das mit der Endlosschleife ist korrekt, aber irrelevant, da dieser Zustand aufgrund meines restlichen codes nie der Fall sein kann.

Wie meinst du das genau? So:

static boolean isValidPath(boolean [][] field, int i, int j, int previ, int prevj) {
		
if(i >= field.length && j >= field[0].length) return true;
		
if(field[i][j] == true) {
			
	System.out.println("Valid i: " + i + ", j: " + j);
	if(i + 1 < field.length && i + 1 != previ) {
		if(isValidPath(field, i + 1, j, i, j)) return true;
	}
	if(j + 1 < field[0].length && j + 1 != prevj) {
		if(isValidPath(field, i, j + 1, i, j)) return true;
	}
	if(i - 1 >= 0 && i - 1 != previ) {
		if(isValidPath(field, i - 1, j, i, j)) return true;
	}
	if(j - 1 >= 0 && j - 1 != prevj) {
		if(isValidPath(field, i, j - 1, i, j)) return true;
	}
			
	return false;
			
} else return false;
}

 

[R3ddy]

Ja genau so meinte ich das. Wenn du jetzt noch die Abbruchbedingung in

if(i == field.length - 1 && j == field[0].length - 1) return true;

abänderst sollte es (hoffentlich) funktionieren.

 

[hubertus1990]

Mit noch einer kleinen zusätzlichen Änderung klappt es nun so
Danke vielmals

static boolean isValidPath(boolean [][] field, int i, int j, int previ, int prevj) {	
		
	if(field[i][j] == true) {
			
		System.out.println("Valid i: " + i + ", j: " + j);
		if(i >= field.length - 1 && j >= field[0].length - 1) return true;	
			
		if(i + 1 < field.length && i + 1 != previ) {
			if(isValidPath(field, i + 1, j, i, j)) return true;
		}
		if(j + 1 < field[0].length && j + 1 != prevj) {
			if(isValidPath(field, i, j + 1, i, j)) return true;
		}
		if(i - 1 >= 0 && i - 1 != previ) {
			if(isValidPath(field, i - 1, j, i, j)) return true;
		}
		if(j - 1 >= 0 && j - 1 != prevj) {
			if(isValidPath(field, i, j - 1, i, j)) return true;
		}
			
		return false;
				
	} else return false;
}