# Labyrinth Wegsuche



## vahnsen (12. Jun 2011)

Guten Tag,

ich soll ein Labyrinth programmmieren was aus einsen(1= der Weg ist begehbar) und aus nullen(0= Blockierung) besteht. Wenn dies getahn ist, soll noch geprüft werden ob es einen Weg von der Startstelle a[0][0] bis zum Endpunkt (Ecke unten rechts) a[5][5] gibt


```
public class Lab {
public static void main(String args []){
		
		int [] a1={1,1,0,1,0};
		int [] a2={0,1,0,1,1};
		int [] a3={0,1,0,1,1};
		int [] a4={0,1,0,1,1};
		int [] a5={0,1,0,1,1};
	
		int [][] matrix = {a1,a2,a3,a4,a5};
		
		toString(matrix);
		
		System.out.println(durchsuche((matrix), 1,1));

}

	public static void toString(int [][] matrix){
		for (int zeile = 0; zeile < matrix.length; zeile++) { // Strg leertaste + enter
			
			 for (int spalte = 0; spalte < matrix[zeile].length; spalte++){
				 
				 System.out.print (matrix [spalte][zeile] + " ");
	}
			
			System.out.println();
	}
}
	public static boolean  durchsuche(int[][] matrix, int i, int j){
		
			if(matrix[i][j] == 1)
			
			return true;
			if(matrix[i][j]== 0 ){return false;}
				

	return durchsuche(matrix,i+1,j)|| durchsuche (matrix,i-1,j)|| durchsuche(matrix,i,j+1)|| durchsuche(matrix,i,j-1);



}




}
```

so weit bin ich schon gekommen. Das Problem ist, glaube ich, das meine "durchsuche" Funktion nicht wirklich rekursiv arbeitet und sie sich immer nur a[1][1] anguckt. Hättet ihr eine Idee wie ich das ändern könnte?


----------



## Marcinek (12. Jun 2011)

Sie wird schon rekrisiv korrekt aufgerufen, aber

du rufst es auf mit 1,1,

Das erste element in einem array ist 0 und nicht 1

Dann schaust du bei durchsuche zunächst ob bei i,j eine 1 steht. Dann gibtst du true zurück und das programm endet.

korrekt sollte hier geprüft werden ob i und j = 4 ist.


----------



## vahnsen (12. Jun 2011)

Also ich hatte es auch mit 0,0 zu aller erst gehabt aber dann spuckt er mir Fehlermeldungen wie
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
	at Lab.durchsuche(Lab.java:31)
	at Lab.durchsuche(Lab.java:37)
	at Lab.main(Lab.java:14)
 aus.


```
if(matrix[i][j]==1)	
			i=i+1;
				if(matrix[i][j]==1)
					i=i+1;
				else 
					j=j+1;
				if(matrix[i][j]==1)
					j=j+1;
					
		
					
				if(matrix[4][4]== 1 ){return true;} // Hier fällt mir leider nicht ein wie ich ihm zum schluss das überprüfen lassen kann. Ich weis das er mir hier immer true ausgeben wird wenn 4,4=1 ist.
				
			
			if(matrix[i][j]== 0 ){return false;}
```

hatte mir das jetzt so gedacht, das er immer i und j überprüfen soll. Wäre das so sinvoll?(also weiter an dem Konzept zu halten)


----------



## Marcinek (12. Jun 2011)

Huuu?

Warum wifst du nun deine erste Lösung weg???

Also die war schon fast gut.

Ende ist 
	
	
	
	





```
if ( i == 4 && j == 4) return true;
```

Klar kommt eine index out of bound exception. Wenn du 
	
	
	
	





```
durchsuche (matrix,i-1,j)
```
 machst, dann hast du 0 -1 = -1 und da gibbet kein array für.

Da muss man noch was schauen  Tipp man kann vorher checken ob i und j überhaupt im labyrinth sich befinden ;D


----------



## vahnsen (13. Jun 2011)

Also dann wirde ich prüfen ob i und j ungleich 0 sind


```
if (matrix[i][j]!=0)
			if(matrix[i+1][j]!=0 || matrix [i][j+1]!=0)
                             i=i+1;
```

das 2. if hab ich gemacht, damit das 

.ArrayIndexOutOfBoundsException: -1  irgendwie weg geht. 

Prinzip, er soll i+1 rechnen damit er beim rekursiven durchgang nicht auf -1 kommt, allerdings lass ich damit das j total außer acht. Kann man denn irgendwie paralel prüfen? also wenn i+1 != 0 dann i=i+1 und wenn j!=0 dann j=j+1


----------



## Marcinek (13. Jun 2011)

Nein

er darf in diese richtung gar nicht rechnen.


----------



## vahnsen (13. Jun 2011)

```
if (matrix[i][j]!=0)
```

das kann ich aber schon als "Start" so bezeichnen oder?


----------



## Marcinek (13. Jun 2011)

naja der start ist 

i=0; j=0

und wenn der bei i=4 und j=4 ankommt, dann exisitiert ein pfad von 0,0 nach 4,4


----------



## vahnsen (13. Jun 2011)

Ja, aber wenn ich bei 0,0 anfange gibt er mir ja -1 aus, also muss ich doch bevor die rekursion das erste mal durchläuft i eins höher setzen?


----------



## Marcinek (13. Jun 2011)

nein

siehe PM


----------



## thorstenthor (13. Jun 2011)

richtig elegant ist die Abbruchbedingung folgendermaßen:


```
if (i >= matrix.length || j >= martix[i].length) {
  return false;
}
if (i == 5 && j == 5) { // oder 4
  return true;
}
if (matrix[i][j] == 0) {
  return false;
}
```

Beim Durchschreiten muss man sich überlegen, ob man von einem Feld aus auch nach links oder oben gehen kann oder nur rechts und unten. Wenn nur nach rechts und unten, dann ist müsste man nicht markieren, welche Felder schon besucht worden sind:


```
return durchsuche(matrix, i + 1, j) || durchsuche(matrix, i, j + 1);
```


----------

