Le mosse del cavallo
Vi viene fornita una griglia 8x8, in cui le righe sono numerate da 0 a 7 dall’alto verso il basso e le colonne da 0 a 7 da sinistra a destra. Un cavallo si trova nella cella
(a, b) della griglia. Il cavallo può muoversi secondo le regole standard degli scacchi, ovvero:- Può spostarsi a forma di “L”, effettuando due passi in una direzione (orizzontale o verticale) e poi uno in direzione perpendicolare.
- Il cavallo non può uscire dal perimetro della griglia 8x8.
Ogni mossa del cavallo ha un costo. Il costo di spostare il cavallo dalla posizione alla posizione è definito come
y⋅r + x⋅c.Data la posizione iniziale del cavallo
(a, b), il vostro compito è calcolare e mostrare il costo minimo necessario per spostare il cavallo da (a, b) a ogni altra cella della griglia.Scrivete un programma che legga in input la posizione iniziale del cavallo e produca in output il costo minimo per ciascuna cella della griglia.
Input
L’input consiste in una singola riga con due interi separati da spazio,
a e b (0 ≤ a, b ≤ 7), che indicano la posizione iniziale del cavallo.Output
Stampate otto righe, ognuna contenente otto interi separati da spazio. L’i-esimo intero nella j-esima riga rappresenta il costo minimo per spostare il cavallo dalla posizione
(a, b) alla posizione (i, j) nella griglia 8x8.Esempi
Ingresso | Uscita |
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