In Kara's Welt gibts es "Inseln", die durch Bäume repräsentiert werden. Zwischen je zwei Inseln ist mindestens ein leeres Feld, das heisst, zwei Inseln berühren einander nicht, nicht einmal diagonal. Zwei Inseln werden Nachbarn genannt, wenn ihre relative Position wie die Bewegung eines Springers im Schach ist. Die folgende Abbildung zeigt alle möglichen Nachbarn der Insel in der Mitte:
Eine Inselgruppe ist eine maximale Menge von benachbarten Inseln. Eine Inselgruppe kann durch einen verbundenen Graphen dargestellt werden, dessen Knoten die Inseln sind, wobei nur die Knoten benachbarter Inseln verbunden sind. Eine Folge von Kanten, die zum Startknoten zurückführt, bildet einen Zyklus. Ein Graph ohne Zyklus ist ein Baum.
Aufgabe 1: Programmieren Sie Kara so, dass er alle Inseln innerhalb einer Baum-Inselgruppe berührt (daran vorbeiläuft), wenn er neben einer der Inseln gestartet wird. Falls die Inselgruppe einen Zyklus enthält, welchen Teil der Inselgruppe wird durch Ihr Programm besucht?
Aufgabe 2: Ändern Sie die Lösung zu Aufgabe 1 so, dass Kara eine Spur von Kleeblättern auf allen Feldern hinterlässt, die er besucht hat. Kara soll anhalten, wenn er den Startpunkt wieder erreicht.
Aufgabe 3: Nachdem Kara gelernt hat, wie er eine Inselgruppe erforschen kann, möchte er nun den gesamten Ozean kennen lernen. Für diese anspruchsvolle Aufgabe sei es ihm erlaubt, Kleeblätter beliebig zu legen und wieder aufzunehmen. Die Idee ist, dass Kara nach der vollständigen Erforschung einer Inselgruppe ins Blaue raus segelt, in der Hoffnung, neue Inselgruppen zu finden. Ist das möglich, sofern Kara im deterministischen Modus ist? Experimentieren Sie mit Kara im nicht-deterministischen Modus, um dieses Problem zu lösen.