Kara Labyrinthproblem (c/c++)

[zNeL]

hallo leute.

ich habe ein problem. in der schule programmieren wir zur zeit mit kara. wir sind nun zu dem problem gekommen, das kara (son kleiner marienkäfer) ein labyrinth durchsuchen soll und dabei den pilz finden soll. dieser kann an jeder stelle des labyrinths ssein, muss aber gar nicht aufzufinden sein.

kara soll den pilz finden, also alle möglichen felder abgehen um den pilz zu finden (er soll auch merken wenn der pilz nicht vorhanden ist).

in dem labyrinth (was aus bäumen besteht) können auch inseln vorkommen, also ein baum, der alleine im labyrinth steht und an dem kein anderer baum grenzt.

als tipp hatten wir schon bekommen, das kara kleeblätter da legt, wo er war, damit er weiß, wo er überall schon war.

bei bedarf kann ich kara auch hochladen, damit ihr es euch einmal anschauen könnt.

würd mich freun, wenn jemand wüsste, wie das problem anzugehen ist.(ob als programmcode oder struktugramm)

hilfestellung von unserm lehrer waren:

-backtraking/tiefensuche

-rekursion

mfg

zNeL

[Guybrush Threepwood]

Was erwartest du jetzt? Das dir jemand ne fertige Lösung liefert?

Bei konkreten Problemen oder Fragen findest du hier gerne Hilfe, aber deine Hausaufgaben wird hier niemand für dich machen. Zumindest nicht ohne entsprechendes Endgeld

[Goos]

hilfestellung von unserm lehrer waren:

-backtraking/tiefensuche

-rekursion

Hilfestellung von mir ist:

Kara ist relativ bekannt

Goos

[Crush]

Laß den Käfer doch einfach immer rechts die Wand entlanglaufen und wenn es eine Abzweigung gibt, wird diese abgewandert. Man muß bestenfalls nur prüfen, ob die Anfangsposition irgendwann erreicht ist (falls es nix zu finden gibt). Ein Beispiel dazu sind die Gegner in Boulderdash, die die freigelegten Gänge nach Dir absuchen.

Falls es Dir hilft, kannst Du beim PQ-Wettbewerb sehen, wie man Backtracking in C/C++ umsetzen kann, allerdings ging es hier nicht um ein Labyrinth, sondern darum ein Logik-Spiel zu lösen - aber irgendwie klappen diese Dinger doch praktisch alle gleich. Überall liegt auch der Sourcecode bei. (natürlich empfehle ich Dir insbesondere meinen Beitrag "Blue and Red" dazu anschauen ).

Ansonsten sollte es zum Thema Backtracking mehr als genug Beispiele im Netz geben.