Pathword Quest
Vous disposez d’une grille de taille
n x n composée de lettres minuscules anglaises. Votre objectif est de déterminer s’il existe un chemin simple dans cette grille qui, lorsqu’on le lit, correspond à la chaîne de caractères s donnée.💡
Un chemin simple peut débuter dans n’importe quelle case de la grille et se déplacer vers une case voisine (haut, bas, gauche ou droite) à chaque étape.
Chaque case ne peut être visitée qu’une seule fois, et il est possible de changer de direction au besoin.
Les lettres rencontrées sur ce chemin doivent former la chaîne
s dans l’ordre.Entrée
La première ligne contient un entier
n (1 ≤ n ≤ 6), indiquant la taille de la grille.Les
n lignes suivantes contiennent chacune n lettres minuscules anglaises, représentant les lettres de chaque case de la grille.La dernière ligne contient une chaîne de caractères
s (1 ≤ |s| ≤ 15), composée de lettres minuscules anglaises.Sortie
Imprimez
YES s’il existe un chemin simple dans la grille formant la chaîne s dans l’ordre. Dans le cas contraire, imprimez NO.Exemples
Entrée | Sortie |
3
a b e
d c f
g h i
abc | YES |
3
a b e
d c f
g h i
abce | NO |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB