Prologin
2024
É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$
