Universität Ulm - Abteilung Angewandte Informationsverarbeitung

 

6. Übungsblatt zur Vorlesung Allgemeine Informatik III

Abgabetermin: Dienstag, 02.12.2003

Labyrinth    (10 Punkte)

Schreiben Sie ein Programm, das Ihnen den Weg aus einem Labyrinth nach der Rechten-Hand-Regel zeigt. Jedes Labyrinth ist rechteckig und maximal 100 x 100 Felder groß. Ein Feld ist als Startfeld, ein weiteres Feld als Endfeld markiert. Alle weiteren Felder sind Gang- bzw. Mauerstücke. Sie können davon ausgehen, daß ein Pfad vom Startfeld zum Endfeld existiert und daß das Startfeld am linken Rand, das Endfeld irgendwo am Rand des Labyrinths liegt.

Beispiele:

5 4
XXXEX
SoooX  S = Startfeld, E = Endfeld
oooXX  X = Mauer, o = Gang
XXXXX

6 4 
XXXEXX
XoooXX  "Ungültig", da das Startfeld nicht am Rand liegt
ooSooX  
XoooXo

3 3
ooX 
SXX    "Ungültig", da kein Pfad von S nach E existiert
XXE

Die Rechte-Hand-Regel

• Man laufe immer so, daß die rechte Hand stets an den Mauerstücken bzw. an den Rändern des Labyrinths entlang geführt wird.
• Dadurch daß Start- und Endfeld am Rand des Labyrinths liegen ist garantiert, daß mit der Rechten-Hand-Regel ein Weg von S nach E gefunden wird.

Das Programm

• Die Größe des Labyrinths ist immer in der ersten Zeile definiert.
• Arbeiten Sie mit einem 2-dimensionalen Array, in das die Daten des Labyrinths eingelesen werden können.
• Implementieren Sie die Rechte-Hand-Regel und geben sie den gefundenen Weg aus (X- und Y-Koordinate).
• Bei der Wegsuche ist eine Variable, welche die aktuelle Laufrichtung enthält, hilfreich.

Beispielausgabe:

  01234
0 XXXEX
1 SoooX
2 oooXX
3 XXXXX

1 0 | 2 0 | 2 1 | 2 2 | 1 2 | 1 3 | 0 3


  012
0 oXE
1 ooo
2 Soo

2 0 | 2 1 | 2 2 | 1 2 | 0 2

Viel Erfolg!