Übungen zu Programmieren II / Allg. Informatik II SS 97
Blatt 8 (19.06.97 - 26.06.97)

Aufgabe 8 (20 Punkte)

Ein klassisches Beispiel für das Backtracking stellt die Suche nach dem Weg durch ein Labyrinth dar.

Realisieren Sie ein Modula-2-Programm, das folgende Aufrufsyntax akzeptiert:

$ lab infile [ outfile ]

• Ein Labyrinth wird beschrieben als zweidimensionales Character-Array.
• Ein Labyrinth wird beschrieben durch Blanks (Weg) und # (Mauer).
• Ein Labyrinth muß genau einen Eingang auf der linken und genau einen Ausgang auf der rechten Seite besitzen.
• Oben und unten muß das Labyrinth abgeschlossen sein.

Das Programm lab soll dann weiter einen rekursiven Algorithmus zur Durchquerung eines Labyrinths realisieren. Markieren Sie dabei den gefundenen Lösungsweg (falls vorhanden) durch ein spezielles Zeichen im Labyrinth, bevor Sie das Labyrinth ausgeben.

Hinweise:

• Wenn Sie jede Eingabezeile durch das Null-Byte (0C oder FROM ASCII IMPORT nul) abschliessen, können Sie die Ausgabe des Labyrinths leicht mit der Funktion FwriteString aus FtdIO realisieren.
• Für Kontrollausgaben kann die Prozedur ShowLab aus dem Modul Labyrinth verwendet werden. Dazu muß dann aber der Typ Labyrinth aus demselben Modul benutzt werden. Um die Ausgabe am Bildschirm festzuhalten, kann die Prozedur Labyrinth.ReadKey verwendet werden.
• Falls Sie das Modul Labyrinth verwenden wollen, sollten Sie Ihre Fehlermeldungen mit der Prozedur Labyrinth.ErrMesg ausgeben. Diese Prozedur gibt die übergebene Fehlermeldung aus und bricht das Programm ab.
• Beispieldateien (lab1, ..., lab7) wie auch die beiden Module Labyrinth.d und Labyrinth.m2 finden Sie wieder im Katalog
  /www/thales/ftp/pub/vorlesungen/ss97/prog/blatt8

Viel Erfolg!