Link to the Past – Épreuve régionale 2015

Niveau 5

Énoncé

J'avais ouï d'une tour
Siégant un peu plus loin
J'ai attrapé mon canasson mes bottes et mon gourdin.

Au cours de ses péripéties habituelles ayant pour but de sauver la princesse Zelda, le vaillant Link a acquis le pouvoir de se rendre dans une version antérieure du monde dans lequel il se meut.

Link cherche à utiliser cette nouvelle faculté pour optimiser ses déplacements, et ainsi en découdre au plus vite avec le grand méchant Ganon.

Il aimerait ainsi connaître la taille du chemin le plus court entre le départ et la sortie des différents donjons qu'il doit parcourir au cours du jeu.

Quand Link est sur une case, ses cinq actions possibles sont donc :

  • Aller au nord ;
  • Aller au sud ;
  • Aller à l'ouest ;
  • Aller à l'est ;
  • Changer de plan temporel (passé → présent ou présent → passé).

Il est impossible d'utiliser la capacité de voyage dans le temps si la case d'arrivée est un mur.

On vous donne le plan des donjons sous forme textuelle, avec :

  • # pour les murs infranchissables
  • . pour les cases où il est possible de se déplacer
  • d la case de départ
  • a la case d'arrivée

Les cases de départ et d'arrivée se trouvent toujours dans la version présente du donjon.

Quel est le nombre minimum d'actions que Link devra effectuer pour sortir des différents donjons passés en entrée ?

Entrée

  • Sur la première ligne, deux entiers m et n séparés par un espace, qui correspondent à la taille du donjon
  • Sur les m lignes suivantes, une représentation de la version présente du donjon (lignes de n caractères).
  • Sur les m lignes suivantes, une représentation de la version passée du donjon (lignes n caractères).

Sortie

  • Le nombre d'actions minimum nécessaire pour arriver à la sortie, ou 0 s'il n'existe aucun moyen de sortir du donjon.

Contraintes

  • 0 < n <= 1000
  • 0 < m <= 1000

Contraintes d'exécution

Utilisation mémoire maximum
5000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
1 6
d.#..a
#...##
Exemple de sortie
7
Commentaire

Sur cette grille de taille 1×6, il faut aller dans le passé pour franchir le mur présent !

Exemple d'entrée
3 7
d....#a
.#####.
.......
###....
######.
.......
Exemple de sortie
8
Exemple d'entrée
2 5
###..
d..#a
.....
###..
Exemple de sortie
0