home
Ein großer und schwerfälliger Tanker soll durch den engen
und gewundenen Zuse-Kanal gesteuert werden. Das Problem dabei ist die große Trägheit des Tankers, dessen Richtung und Geschwindigkeit sich nur allmählich ändern können. Die Tankersteuerung soll programmiert werden.

Dazu nehmen wir an, dass …

  • eine Karte des Kanals vorliegt, die in Planquadrate aufgeteilt
    ist. Jedes Planquadrat ist entweder für Schiffe
    befahrbar oder nicht.
  • der Tanker sich zu jeder vollen Minute genau in der
    Mitte eines Planquadrats im Kanal befindet. Zwischenpositionen
    interessieren nicht.
  • der Tanker sich nur im Wasser bewegen kann: die Verbindungsstrecke
    zwischen zwei Positionen, die zu aufeinanderfolgenden
    Minuten eingenommen werden,
    darf nur befahrbare Planquadrate durchqueren.
Eine Bewegung des Tankers innerhalb einer Minute von einem Planquadrat zu einem anderen kann durch die Differenzen zwischen den horizontalen bzw. vertikalen Koordinaten der Planquadrate beschrieben werden. Ein Beispiel gibt die folgende Abbildung: Die Bewegungvon Planquadrat (3,3) zu Planquadrat (4,2) wird durch das Paar von Bewegungswerten [1,-1] beschrieben.
Die Trägheit wird nun so modelliert, dass sich die Bewegungswerte für die nächste Minute von den vorigen jeweils höchstens um 1 unterscheiden dürfen. Im obigen Beispiel zeigen die von Planquadrat (4,2) ausgehenden Pfeile die in der nächsten Minute aufgrund dieser Regelung erlaubten Bewegungen. Die roten Pfeile entsprechen dabei unmöglichen Bewegungen, die nicht befahrbare Quadrate durchqueren.
Gegeben sind nun zwei Planquadrate, an denen der Tanker
seine Fahrt beginnen bzw. beenden soll. Am Start und am
Ziel soll der Tanker still liegen, also „ohne Fahrt“ sein, wie
es in der Sprache der Seeleute heißt. (Wie kann man diese
Bedingung mit Hilfe von Bewegungswerten ausdrücken?)
Beispielkanal:
 
Aufgabe
Schreibe ein Programm, das bei gegebenem Kanal für ein Startplanquadrat und ein Zielplanquadrat eine Fahrt von möglichst kurzer Dauer berechnet. Ermittle mit seiner Hilfe Fahrten für drei unterschiedliche Paare von Start- und Zielplanquadraten; eine dieser Fahrten soll im oben abgebildeten Beispielkanal vom mit S markierten Planquadrat zu dem mit Z markierten Planquadrat führen, die anderen
dürfen auch durch andere Kanäle gehen. Stelle die Eingabedaten grafisch dar und zeichne die gefundenen Fahrten in geeigneter Weise ein.