Histoire

Pour son 10^e travail, Eurysthée demanda à Hercule de lui rapporter les bœufs de Géryon. Celui-ci, un géant à trois torses, possédait un troupeau de magnifiques bœufs. Naturellement, il veillait jalousement sur son troupeau, aidé par Orthros, son chien tricéphale, et Eurythion, son dragon à sept têtes.

La légende raconte qu'Hercule tua ou assomma les trois gardiens avant de s'emparer du troupeau... mais la vérité est toute autre. Géryon vivait et gardait son troupeau sur un plateau, entouré de falaises. Il n'avait pas besoin de clôtures car le vide entourait complètement le lieu où résidait le troupeau. Hercule procéda par ruse, et il creusa un tunnel qu'il fit émerger en plein milieu du champ. Il emprunta ce tunnel, et parvint jusqu'au troupeau où les 3 gardiens monstrueux étaient endormis. Là, il essaya de guider les bœufs un à un pour leur faire emprunter le tunnel.

Les bœufs de Géryon ne brillaient pas par leur esprit d'initiative... et Hercule avait bien du mal à les guider. Pour chaque bœuf, il pouvait lui ordonner de partir tout droit vers le nord, vers le sud, vers l'est ou vers l'ouest. Une fois l'ordre donné, le bœuf fonçait dans la direction indiquée par Hercule. Il pouvait alors se produire une des quatre choses suivantes :

• Soit le bœuf ne rencontrait aucun obstacle, arrivait au bord de la falaise, et tombait. Le vacarme réveillait les gardiens faisant échouer Hercule dans sa quête.
• Soit le bœuf ne rencontrait aucun obstacle en direction du tunnel creusé par Hercule. Dans ce cas, il empruntait le tunnel, puis était récupéré par les marins, puis embarqué sur le navire d'Hercule.
• Soit le bœuf fonçait dans un autre bœuf, ce qui avait pour seul effet de l'arrêter net.
• Soit le bœuf percutait un des trois gardiens, ce qui réveillait celui-ci, faisant échouer Hercule dans sa quête.

L'objectif de ce défi est, connaissant la position de tous les bœufs du troupeau, et des 3 gardiens, de trouver la bonne séquence d'ordres que doit donner Hercule pour récupérer le maximum de bœufs, sans éveiller de gardien.

Pour ceci, une carte (vue de dessus du lieu où sont gardés les bœufs) vous est fournie. Par exemple :

.........
.A...E..@
.........
..@.@....
....+...F
.........
....B....
.C...D...
.........

Sur cette carte (le terrain est toujours carré, mais sa taille peut varier), la sortie du tunnel d'Hercule est indiquée par +, les 3 gardiens sont indiqués par @, et le bœufs sont repérés par les lettres A à F.

Voyons un peu quelles sont les possibilités :

• Si Hercule ordonne au bœuf A de partir vers le nord ou vers l'ouest, il tombera et la partie sera perdue.
• Si Hercule ordonne au bœuf E de partir vers l'est, il réveillera un des gardiens, et la partie sera perdue.
• Si Hercule ordonne au bœuf A de partir vers le sud, il sera arrêté par le bœuf C. La situation sera alors:

  .........
  .....E..@
  .........
  ..@.@....
  ....+...F
  .........
  .A..B....
  .C...D...
  .........
  

• Si Hercule demande au bœuf B de partir vers le Nord, il empruntera le tunnel et sera récupéré par l'équipage d'Hercule.

Testez votre code

Dans l'exemple qui précède, Hercule ne peut pas faire mieux que récupérer 4 bœufs. Il peut toutefois opérer de plusieurs manières pour arriver à ce résultat. En voici une :

.........
.A...E..@
.........
..@.@....
....+...F
.........
....B....
.C...D...
.........

Ordre : bœuf E au sud (ES)

.........
.A......@
.........
..@.@....
....+...F
.........
....BE...
.C...D...
.........

Ordre : bœuf B au nord (BN) => 1 bœuf embarqué

.........
.A......@
.........
..@.@....
....+...F
.........
.....E...
.C...D...
.........

Ordre : bœuf A au sud (AS)

.........
........@
.........
..@.@....
....+...F
.........
.A...E...
.C...D...
.........

Ordre : bœuf A à l'est (AE)

.........
........@
.........
..@.@....
....+...F
.........
....AE...
.C...D...
.........

Ordre : bœuf C à l'est (CE)

.........
........@
.........
..@.@....
....+...F
.........
....AE...
....CD...
.........

Ordre : bœuf A au nord (AN) => 2 bœufs embarqués

.........
........@
.........
..@.@....
....+...F
.........
.....E...
....CD...
.........

Ordre : bœuf C au nord (CN) => 3 bœufs embarqués

.........
........@
.........
..@.@....
....+...F
.........
.....D...
.....C...
.........

Ordre : bœuf F à l'ouest (FO) => 4 bœufs embarqués

.........
........@
.........
..@.@....
....+....
.........
.....D...
.....C...
.........

Une solution possible à cet exemple serait de donner la séquence d'ordres suivante : ESBNASAECEANCNFO