mcjayjay

Hi Leute,

Ich zerbreche mir schon den ganzen abend den Kopf über folgendes Problem:

ich habe ein Gitter (zur Anschaung sage ich mal ein Schachbrett mit 9*9 feldern).

- - : - - - : - -
- - - - - - - - -
- : - - - : - - -
- - - - - - - - :

Auf diesem Schachbrett stehen nun Figuren. hier durch ':' makiert.
Nun gehe ich von der ersten Figur aus (koordinate 1;3).

Wie bekomme ich nun raus welche Figur den kürzesten Abstand zu der Ausgangsfigur hat, wenn die Figuren waagerecht, senkrecht und diagonal zwischen den feldern laufen können.

In meinem Beispiel logischerweise die Figur auf 3;2

Wenn jemand einen Forschlag hätte oder vtl einen Algorithmus für derartige Probleme kennt würde mich das sehr freuen.

Mister Ad

Montellese

Du musst zuerst ne Variable setzen, wo du den kürzesten gefundenen Weg speicherst. Dann musst du halt alle möglichen Richtungen ablaufen und sobald du auf eine Figur triffst, vergleichst du die Distanz mit dem Wert in der Variable. Wenn der Wert grösser ist, versuchst du eine andere Richtung, ansonsten speicherst du den neuen Wert in die Variable und versuchst die nächste Richtung, bis du alle durch hast.

Oder du liest alle Figuren mit ihren Positionen aus und wenn du dann eine Figur als Startpunkt festgelegt hast, probierst du alle anderen Figuren durch und schaust zuerst, ob sie überhaupt waagerecht, senkrecht oder diagonal zur Startfigur ist und wenn ja, kannst du die Distanz ja einfach aus den Koordinaten berechnen. Der Rest mit der Variable ist dann gleich wie beim ersten Ansatz.

David

Wenn Du in jedem Durchlauf die bekannten Pfade um jeweils einen Schritt (jeweils in alle möglichen Richtungen) erweiterst, ist der erste Pfad, mit dem Du das Ziel erreichst auch der kürzeste; es gibt keinen kürzeren Pfad.
Breitensuche - Wikipedia

mcjayjay

thx für die schnelle Antwort, da kann ich doch schonmal was mit anfangen.