Thésée et l'Aibo – Épreuve régionale 2010

ÉNONCɶ

Joseph Marchand passe ses vacances en Crète, et il est en train de visiter le fameux labyrinthe où Thésée avait occi le Minotaure. Malheureusement, il semble que la mythologie ait un peu embelli le rôle de Thésée, et que le Minotaure soit en réalité... toujours vivant !

Bon, on vous rassure. En fait, c'est pas un Minotaure, c'est un Aibo que le fils de Joseph Marchand a programmé pour pousser des mugissements de taureau. Mais ça, Joseph Marchand ne le sait pas... Il veut donc échapper à ce qu'il suppose être un Minotaure. Au bruit, il se rend compte que le Minotaure a un comportement assez prédictible (normal, c'est un robot !). À chaque fois que Joseph fait un pas, le Minotaure en fait au plus deux, et chaque pas du Minotaure suit un algorithme déterministe : il regarde d'abord s'il peut se rapprocher de Joseph Marchand horizontalement ; si oui, il le fait. Sinon, s'il peut se rapprocher verticalement, il le fait.

Ce comportement étant assez basique, cela signifie que le Minotaure peut resté bloqué pendant que Joseph bouge (par exemple, s'ils sont sur la même ligne, séparés par un mur vertical, le Minotaure restera bloqué tant que Joseph restera sur la ligne). Il a donc une chance de s'en sortir...

Bon, tout ça est assez obscur. On vous propose plutôt de jouer (cette appliquette a été réalisée par Toby Nelson). Les touches utiles sont les flèches, D pour sauter un tour, et N pour passer au niveau suivant.

There is a Java applet here. To use it, you need a Java aware browser with Java enabled.

Précision : durant un "tour" (une occasion que Joseph aurait de faire un pas), Joseph peut choisir de "passer son tour" et de ne pas bouger en laissant le Minotaure se rapprocher. Les deux personnages ne se déplacent que dans les quatre directions.

Quelle est la longueur du plus court chemin conduisant à une sortie (une case du bord du labyrinthe sans mur dans une direction qui permet d'en sortir) que Joseph peut prendre pour échapper au Minotaure ?

ENTRÉE¶

• On vous donne les entiers N et M, nombre de lignes et de colonnes du labyrinthe.

• Suivent N lignes de M chiffres. Chacun est le OU binaire de :

• 1 si la case a un mur au nord (vers la ligne du dessus) ;

• 2 si la case a un mur à l'est ;
• 4 si la case a un mur au sud ;

• 8 si la case a un mur à l'ouest.

• Sur les deux dernières lignes, on vous donne les coordonnées (ligne puis colonne) de la position initiale de Joseph, puis de la position initiale du Minotaure.

LIMITES¶

• N, M <= 40

SORTIE¶

• La longueur du plus court chemin permettant à Joseph de sortir du labyrinthe sans se faire mordre par l'Aibo, ou -1 s'il n'y en a pas (les "tours" où Joseph ne se déplace pas comptent pour un déplacement).

Ce jeu a été conçu par Robert Abott.