Énoncé

On se donne un labyrinthe en entrée dont le plan est connu.
Il contient 100 fois 100 cases.
Les cases du labyrinthe sont numérotées ligne par ligne, de bas en haut et de gauche à droite.
Ainsi, la case 0 est au coin inférieur gauche, la case 99 au coin inférieur droit, et la case 9999 au coin supérieur droit.

Dans ce labyrinthe sont placées 9 pièces d'or, dont on connait les emplacements.
Dans cet exercice, on cherche à récupérer toutes les pièces d'or en faisant un minimum de mouvements (un mouvement étant le déplacement d'une case à une case adjacente entre lesquelles il n'y a pas de mur).

Entrée

L'entrée comporte sur les 10.000 premières lignes les cases auxquelles on peut accéder à partir de la case 0, puis 1 ... jusqu'à 9999 (dans l'exemple donné ci-dessous, on voit qu'on peut se déplacer de la case 0 à la case 1 et à la case 100, puis de la case 1 à la case 2, 101 ou 0 etc).
Les numéros sont séparés par des espaces.
La ligne suivante contient la liste, séparée par des espaces, des 9 pièces d'or à aller chercher (il n'y a pas de pièce sur la case de départ).
Enfin, on commencera toujours sur la case 0 du labyrinthe.
On considère que toutes les pièces ont été prises lorsque les 9 cases contenant des pièces d'or ont été visitées : il n'y a pas besoin de revenir au point de départ du labyrinthe.

Notez aussi que les pièces sont toujours atteignables !

Sortie

La sortie est le nombre minimal de mouvements pour aller chercher toutes les pièces d'or, suivi d'un retour à la ligne.

Exemple

EntréeSortie

Squelette CamlLight

Squelette OCaml