Moin miteinander,
ich habe folgendes Problem:
Die Aufgabe lautet, ein Labyrinth zu lösen. Das Labyrinth ist ein 2-D Array, wobei jedes Feld entweder eine Mauer oder ein Weg ist. Das Lösungsprinzip ist mir klar: Ich überprüfe vom Startfeld aus die angrenzenden Felder ob Mauer oder Weg. Den ersten Weg nehme ich und prüfe von da aus von Neuem. Ist das neue Feld ein Randfeld, ist das Labyrinth gelöst. Soweit so gut. Mein Algorithmus tut das auch. Nur sobald er am Rand angekommen ist, macht er weiter :-(. Und besucht alle noch nicht besuchten Felder im Labyrinth und bricht erst ab, wenn er überall war. Hier mein Code zum Lösen des Labyrinths (ich hoffe, der reicht. Das restliche Programm ist ziemlich umfangreich):
ich habe folgendes Problem:
Die Aufgabe lautet, ein Labyrinth zu lösen. Das Labyrinth ist ein 2-D Array, wobei jedes Feld entweder eine Mauer oder ein Weg ist. Das Lösungsprinzip ist mir klar: Ich überprüfe vom Startfeld aus die angrenzenden Felder ob Mauer oder Weg. Den ersten Weg nehme ich und prüfe von da aus von Neuem. Ist das neue Feld ein Randfeld, ist das Labyrinth gelöst. Soweit so gut. Mein Algorithmus tut das auch. Nur sobald er am Rand angekommen ist, macht er weiter :-(. Und besucht alle noch nicht besuchten Felder im Labyrinth und bricht erst ab, wenn er überall war. Hier mein Code zum Lösen des Labyrinths (ich hoffe, der reicht. Das restliche Programm ist ziemlich umfangreich):
Java:
public boolean solve(int x, int y) {
int aktuellesX = x;
int aktuellesY = y;
/* Am Rand angekommen? */
if (aktuellesX == 0 || aktuellesY == 0 || aktuellesX == this.getXDimension() - 1 || aktuellesY == this.getYDimension() - 1) {
return true;
}
/* Alle Richtungen versuchen */
if (!fields[aktuellesX + 1][aktuellesY].isWall() && !fields[aktuellesX + 1][aktuellesY].isVisited()) {
fields[aktuellesX + 1][aktuellesY].setVisited(true);
solve(aktuellesX + 1, aktuellesY);
}
if (!fields[aktuellesX][aktuellesY + 1].isWall() && !fields[aktuellesX][aktuellesY + 1].isVisited()) {
fields[aktuellesX][aktuellesY + 1].setVisited(true);
solve(aktuellesX, aktuellesY + 1);
}
if (!fields[aktuellesX - 1][aktuellesY].isWall() && !fields[aktuellesX - 1][aktuellesY].isVisited()) {
fields[aktuellesX - 1][aktuellesY].setVisited(true);
solve(aktuellesX - 1, aktuellesY);
}
if (!fields[aktuellesX][aktuellesY - 1].isWall() && !fields[aktuellesX][aktuellesY - 1].isVisited()) {
fields[aktuellesX][aktuellesY - 1].setVisited(true);
solve(aktuellesX, aktuellesY - 1);
}
return false;
}