Dr. Andreas Borchert Abteilung Angewandte Informationsverarbeitung 12.01.2005
Norbert Heidenbluth Blatt 11






Allgemeine Informatik I für Mathematiker/Wirtschaftsmathematiker
(WS 2004/2005)


Abgabetermin: 19. Januar 2005

Aufgabe 21: Auf der Suche nach Klausuren (10 Punkte)

Ihr Entsetzen über die letzte Matheklausur haben Sie an Silvester mit einem kräftigen Schluck Cuba Libre hinuntergespült, und nach einigen weiteren Gläsern Hochprozentigem hatten Sie dann eine Idee:

Vielleicht gibt es ja in den verwirrenden Gängen im Keller der Uni einige Stellen, an denen die Klausuren lagern. Da wäre es doch schön, wenn man rechtzeitig vor dem nächsten Klausurtermin mal (heimlich im Dunkeln, versteht sich!) danach suchen ginge$\ldots$

Dieser Gedanke verfolgt Sie nun also seit Silvester, und deshalb programmieren wir in diesem Übungsblatt mal eine virtuelle Suche nach Klausuren:

• Gegeben sei eine Datei, die einen Irrgarten (= Uni-Keller) beschreibt. ``X'' steht dabei für ``Wand'' und ein Leerzeichen bedeutet ``freier Weg''.

  Der Name dieser Datei kann zu Beginn des Programms eingegeben werden.

• Ein Irrgarten ist bei uns stets rechteckig, d.h. alle Zeilen der einzulesenden Datei müssen gleich lang sein.

• An einem der vier Seiten des Irrgartens muß es einen Eingang (Leerzeichen) geben.

• In einem Irrgarten können an unterschiedlichen Positionen die Klausuren (= Schätze) liegen. Diese sind mit einem ``T'' (für treasure) markiert.

• Um durch den Irrgarten zu navigieren, können Sie jeweils einen Schritt nach Norden, Osten, Süden oder Westen machen, wobei dies natürlich nur geht, wenn dort keine Wand steht und Sie durch diesen Schritt nicht den Irrgarten verlassen würden.

• Zu Beginn des Spiels ist Ihre Position (selbstverständlich) der Eingang.

• Da Ihre Klausursuche natürlich heimlich stattfinden muß, haben Sie nur das Licht Ihrer Taschenlampe zur Verfügung. Somit sehen Sie nicht den gesamten Irrgarten, sondern nur den Bereich um Sie herum und den bisher besuchten Bereich.

• Der Bereich ``um Sie herum'' soll aus all den Positionen bestehen, die Sie mit einem Schritt in eine der Himmelsrichtungen erreichen können sowie aus den diagonal liegenden ``Ecken''.

  (Als Anregung, wie dies optisch umgesetzt werden kann, können Sie sich das Beispiel anschauen. Dort ist der bislang nicht besuchte bzw. gesehene Bereich durch ein ``?'' dargestellt.)

• Dies bedeutet, daß Positionen, die Sie mal gesehen oder gar besucht haben, für den Rest der Suche sichtbar bleiben.

• Positionen, die Sie bereits besucht haben, werden entsprechend markiert (beispielsweise mit einem Punkt).

Schreiben Sie nun ein Oberon-Programm, mit dem Sie auf die zuvor beschriebene Weise durch einen solchen Irrgarten navigieren können, um alle dort versteckten Klausuren zu finden! Das Programm sollte beendet werden, wenn die letzte Klausur gefunden wurde.

Hinweise

• Dieses Blatt ist zur Aufteilung innerhalb Ihrer Gruppe gedacht! Machen Sie sich daher zunächst Gedanken über die zu verwendende Datenstruktur und teilen Sie dann die Implementierung der benötigten Programmkomponenten untereinander auf.

• Wie in den letzten Übungsblättern auch, dürfen Sie keine globalen Variablen verwenden!

• Es sind mehrere Fehlerfälle beim Einlesen des Irrgartens denkbar, so zum Beispiel:
  • Es ist kein Eingang vorhanden.
  • Der eingelesene Irrgarten ist nicht rechteckig.
  • In der Beschreibung des Irrgartens kommen ungültige Zeichen vor.
  • Die Beschreibung des Irrgartens enthält eine leere Zeile.

  Ihr Programm sollte Fehler wie diese erkennen und entsprechend darauf reagieren.

• Auf unserem FTP-Server finden Sie einerseits wieder eine Beispielimplementierung dieses Programms sowie andererseits einige Beispielirrgärten, mit denen Sie Ihr Programm testen können. Die Dateien good.maze*-Dateien bezeichnen dabei gültige Irrgartenbeschreibungen, die bad.maze*-Dateien beinhalten fehlerhafte Beschreibungen.

• Aus gut unterrichteten Kreisen hört man, daß die nächsten Matheklausuren nicht im Uni-Keller gelagert werden, sodaß Sie sich auf die rein virtuelle Suche im Rahmen dieses Übungsblattes beschränken können und nicht selbst zur Taschenlampe greifen brauchen$\ldots$ ;-) !

Viel Erfolg!