Hallo Freunde,
ich versuche schon seit Tagen das Labyrinthproblem zu lösen, mittels Backtracking.
1.Paar Methoden fehlen mir noch, wäre echt freundlich wenn mir jemand helfen könnte.
2.Falls Weg gefunden wird soll das Labyrith wie in TXT ausgegeben werden und der Weg soll mit "O"s gekenzeichnet sein.
3.Falls kein Weg, soll "Kein weg gefunden" ausgegeben werden.
"+" ist die Startposition.
4.Das Labyrith soll als Textdatei eingelesen werden:
java Labyrinthsuche labyrinth.txt .
//LabyrinthSuche.java
import java.io.*;
import java.util.StringTokenizer;
/** Findet den Weg ausgehend von einem Startpunkt
aus einem Labyrinth heraus. Das Labyrinth wird
mittels einer ASCII-Datei eingelesen und per
Backtracking-Mechanismus ein moeglicher Weg
gesucht
*/
public class LabyrinthSuche{
/** Das Labyrinth wird mit Hilfe der folgenden Konstanten definiert */
private final static char path = ' ';
private final static char wall = '*';
private final static char start = '+';
private final static char visited = '.';
private final static char foundway = 'O';
/** Das Labyrinth wird mittels eines 2-dimensionalen Arrays dargestellt */
char[][] labyrinth;
/** Hoehe und Breite des Labyrinths */
private int height;
private int width;
/** Die Koordinaten des Startpunktes*/
private int start_x;
private int start_y;
/** Die Koordinaten des Ausgangs*/
private int exit_x;
private int exit_y;
/*************************************************************************
* HIER BEGINNEN IHRE METHODEN... *
* ... *
* ... *
*************************************************************************/
/*************************************************************************
* ... *
* ... *
* HIER ENDEN IHRE METHODEN... *
*************************************************************************/
/** liest ein Textfile mit Namen filename ein
und betrachtet dies als Labyrinth */
private boolean readFile(String filename){
/** temporaere Variable */
char c = ' ';
FileReader fr = null;
BufferedReader in = null;
/** Hier wird versucht, die Datei zu oeffnen */
try{
fr = new FileReader(filename);
in = new BufferedReader(fr);
}catch(FileNotFoundException fnfe){
System.out.println("File not found");
return false;
}
/** Die Datei ist vorhanden
Wir versuchen zeilenweise den Inhalt auszulesen und
anhand der vordefinierten Konstanten unserem Labyrinth
zuzuweisen */
try{
String s = in.readLine();
StringTokenizer st = new StringTokenizer(s);
width = Integer.parseInt(st.nextToken());
s = in.readLine();
st = new StringTokenizer(s);
height = Integer.parseInt(st.nextToken());
labyrinth = new char[height][width];
for (int line=0; line < height; line++){
s= in.readLine();
for (int column=0; column < width; column++){
c = s.charAt(column);
switch(c){
case start:
start_x = column; // Die Startposition x-Koord
start_y = line; // Die Startposition y-Koord
labyrinth[line][column] = path;
break;
case wall:
case path:
labyrinth[line][column] = c;
break;
default:
System.out.println("Falsche Eingabe!");
return false;
}
} // end for column
} // end for line
} catch(java.io.IOException ioe){
System.out.println("IO Exception");
return false;
}
return true;
} // end for readFile()
/** Es wird anhand einer Initialisierungsdatei ein Labyrinth erzeugt
und der Suchvorgang nach einem Ausgang gestartet */
public static void main(String[] args){
if(args.length == 0){ // es wurde kein Dateiname angebeben
System.out.println("usage java LabyrinthSuche <file>");
System.exit(0);
}
LabyrinthSuche ourlab = new LabyrinthSuche();
/* die Datei konnte aus irgendeinem Grund nicht gelesen werden */
if(!ourlab.readFile(args[0])){
System.out.println("Read error while reading " + args[0]);
System.exit(1);
}
if (!ourlab.findWayOut()){
System.out.println("Es existiert kein Weg zum Ausgang");
}else{
System.out.println("Ausgang gefunden!");
System.out.println("Spalte: " + ourlab.getExit("column"));
System.out.println("Zeile: " + ourlab.getExit("line"));
System.out.println(ourlab);
}
} // end for main()
} // end for class LabyrinthSuche
------------------------------------
labyrinth.txt
20
20
* ******************
* * ******* *****
* * * * * *
* ***** * ** *
*** * ** ** *
******* * ******* *
* ***** * * *
* * **** ** ** **
*** ** **
* **+ * * ** **
* ** * *** *** **
** * *** * *** **
* ***** * ** **
* ** ****** *
* *** * * ***
* **** * * ****
* * * *** ****
* * *** * * ******
* * ** * *
********************
Karo Gast |
