Die Züge des Springers
Du hast ein 8×8-Gitter, bei dem die Zeilen von oben nach unten mit 0 bis 7 und die Spalten von links nach rechts ebenfalls mit 0 bis 7 nummeriert sind. Auf diesem Gitter befindet sich ein Springer in der Zelle
(a, b). Der Springer kann sich nach den üblichen Schachregeln bewegen, die folgendermaßen definiert sind:- Er bewegt sich in einer „L“-Form: zuerst zwei Felder in eine Richtung (horizontal oder vertikal), dann ein Feld senkrecht dazu.
- Er darf das 8×8-Gitter nicht verlassen.
Jeder Zug des Springers hat Kosten. Die Kosten für den Zug des Springers von Position zu Position sind definiert als
y⋅r + x⋅c.Ausgehend von der Anfangsposition
(a, b) sollst du die minimalen Kosten berechnen, um den Springer von (a, b) zu jeder anderen Zelle des Gitters zu bewegen.Schreibe ein Programm, das die Anfangsposition des Springers als Eingabe nimmt und für jede Zelle des Gitters die minimalen Kosten ausgibt.
Eingabe
Die Eingabe besteht aus einer einzelnen Zeile mit zwei durch Leerzeichen getrennten ganzen Zahlen
a und b (0 ≤ a, b ≤ 7), welche die Anfangsposition des Springers angeben.Ausgabe
Gib acht Zeilen aus, in denen jeweils acht durch Leerzeichen getrennte ganze Zahlen stehen. Die i-te Zahl in der j-ten Zeile repräsentiert die minimalen Kosten, um den Springer von
(a, b) zur Position (i, j) auf dem 8×8-Gitter zu bewegen.Beispiele
Eingabe | Ausgabe |
1 1 | 13 11 11 3 17 29 43 53
11 0 13 14 19 18 41 64
11 13 9 5 15 31 45 55
3 14 5 22 23 26 45 72
17 19 15 23 25 43 59 73
29 18 31 26 43 58 69 98
43 41 45 45 59 69 97 123
53 64 55 72 73 98 123 146 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB