|
|
|
EL CAVALL DEL ESCACS
El moviment del cavall en el joc dels escacs és un moviment amb propietats molt curioses. Recordem que aquest moviment és sempre una combinació de dues caselles en una direcció seguit d'una casella en una direcció perpendicular, sempre que aquesta casella final estigui dintre del tauler. D'aquesta forma, per un cavall situat prop del centre del tauler hi ha 8 possibles moviments, en canvi, per un cavall situat just en una cantonada n'hi ha només 2, com es pot contemplar a la figura:
El problema que ens plantegem és el següent:
Donades dues caselles, una casella inicial i una casella final, trobar
el nombre mínim de moviments que ha de fer un cavall per anar de
la primera a la segona.
Fixarem la següent notació: cada casella
es representa per dos nombres enters que representen la fila i la columna.
La casella superior esquerra serà la casella (0,0) i la casella
inferior dreta serà la casella (7,7).
El fitxer d'entrada serà un fitxer de text anomenat:
CAVALL.IN
que contindrà a la primera línia, separades
per un espai, la fila i la columna de la casella inicial, i a la segona
línia, també separades per un espai, la fila i la columna
de la casella final. Les dades de les caselles inicials i finals estan
dintre del tauler (no és necessari fer la comprovació).
El fitxer de sortida serà un fitxer de text anomenat:
CAVALL.OUT
amb un sol nombre enter més gran o igual a 0
que indicarà el nombre mínim de moviments per arribar de
la casella inicial a la casella final. En el cas de que ambdues caselles
coincideixin, el nombre mínim de moviments serà 0.
EXEMPLES:
|
|
|
|
0 1
5 4 |
4 |
|
2 3
2 3 |
0 |
Tornar