Labyrinth Wegsuche

V

vahnsen

Mitglied
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

Java: 
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?
 
M

Marcinek

Gast
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.
 
V

vahnsen

Mitglied
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.

Java: 
				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)
 
Zuletzt bearbeitet:
M

Marcinek

Gast
Huuu?

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

Also die war schon fast gut.

Ende ist
Code: 
if ( i == 4 && j == 4) return true;

Klar kommt eine index out of bound exception. Wenn du
Code: 
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
 
V

vahnsen

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

Java: 
		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
 
Zuletzt bearbeitet:
M

Marcinek

Gast
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
 
V

vahnsen

Mitglied
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?
 
T

thorstenthor

Bekanntes Mitglied
richtig elegant ist die Abbruchbedingung folgendermaßen:

Java: 
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:

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

Aktuelle Jobs

Neue Themen


Oben