The wizard escape – Épreuve régionale 2022

Niveau 3

Énoncé

Notre fabuleux sorcier Gantrufle se réveille dans une pièce étrange. Plongé dans l'obscurité, il apperçoit au loin la sortie. Entre lui et son échapatoire toutefois, de sombres tours s'élèvent dans la pénombre. Ces tours, il les reconnait : s'il se situe sur l'une des 8 cases voisines à la tour (diagonales compries), un sort explosif se chargera de le réduire en bouillie !

En tatonnant à travers sur le mur, il trouve l'interrupteur et soudain les torches s'allument (les fameuses torches LED connectées, il en entendu parlé au dernier Forum des Incantateurs Chevronés). Au sol, dispersé à travers la pièce, des Invisibulus Pamalus ! Des potions d'invisibilité qui permettent de parcourir une distance de Manhattan$^1$ de 2 cases parfaitement masqué, et donc invulnérable à la détection perçante des tours explosives. Tellement invulnérable qu'il peut même passer à travers la tour lorsqu'il en boit ! Gantrufle étant, malgré son âge, plutôt vif, s'il atteint une potion ou la sortie dans la zone du sort explosif, on prendra en compte l'action de la tour en dernier.

Seulement voilà, il y a beaucoup de tours, et peu d'espace. Le sorcier décide de vous invoquer pour l'aider à trouver un chemin. Pour ne pas lui rendre la tâche trop simple non plus, nous ne décidez de lui indiquer que s'il existe ou non un chemin pratiquable entre lui et la sortie.

Il accepte et vous dessine la salle: c'est une matrice carrée, le sorcier se trouve dans le coin sud-ouest. Il inscrit quelques symboles dans les cases et vous indique ce qu'ils représentent:

  • Une case libre est représentée par un # ;
  • Une tour par un T ;
  • Une potion par un P ;
  • La sortie par un @.

Finalement, Gantrufle vous précise qu'avec ses quelques années (il a récemment fété ses 130 ans !), sa hanche ne lui permet pas de bondir en diagonale, il ne peut donc se déplacer que devant et derrière lui, à sa droite ou à sa gauche.

Peut-il s'en sortir ?

$^1$On rappelle que la distance de Manhattan est la distance entre deux points sur un quadrillage en utilisant uniquement des déplacements horizontaux et verticaux

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : t, la taille de la salle.
  • Sur les lignes suivantes, une liste de t éléments : s, la matrice carrée représentant la salle.
    • Une ligne par élément de la liste : une liste de t caractères juxtaposés.

Sortie

Afficher "Oui" s'il existe un chemin vers la sortie, "Non" sinon.

Contraintes

  • $2 \le t \le 100$

Contraintes d'exécution

Utilisation mémoire maximum
100 kilo-octets
Temps d'exécution maximum
300 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
####@
#T#T#
#####
####P
#####
Exemple de sortie
Oui
Commentaire

En colorant les zones inatteignable à cause des tours en rouge, les zones protégée par une prise de potion en jeune, la sortie en vert et notre sorcier en bleu, on peut représenter cette configuration comme ceci :

Dans ce labyrinthe, le sorcier peut s'échapper en se dirigeant d'abord vers la potion à sa droite, puis vers le haut pour atteindre la sortie.

Exemple d'entrée
5
####@
#T#T#
#####
#####
####P
Exemple de sortie
Non
Commentaire

Dans cette configuration:

Il n'existe aucun chemin permettant au sorcier de s'échapper sans traverser au moins une case dans le rayon d'action d'une tour sans être invisible.