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.

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

To check your solution you need to sign in
Sign in to continue