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.