Pathword Quest
Se te proporciona una cuadrícula de tamaño
n x n compuesta de letras minúsculas del alfabeto inglés. Tu tarea consiste en determinar si existe un camino simple en esta cuadrícula que pueda leerse como la cadena s dada.💡
Un camino simple comienza en cualquier celda de la cuadrícula y se mueve a una celda adyacente (arriba, abajo, izquierda o derecha) en cada paso.
El camino solo puede visitar cada celda una vez y puede cambiar de dirección según sea necesario.
Las letras en el camino deben formar la cadena
s cuando se lean en orden.Entrada
La primera línea contiene un número entero
n (1 ≤ n ≤ 6), que representa el tamaño de la cuadrícula.Las siguientes
n líneas contienen n letras minúsculas del alfabeto inglés cada una, que representan las letras en cada celda de la cuadrícula.La última línea contiene una cadena
s (1 ≤ |s| ≤ 15), compuesta de letras minúsculas del alfabeto inglés.Salida
Imprime
YES si existe un camino simple en la cuadrícula que forme la cadena s al leerse en orden. De lo contrario, imprime NO.Ejemplos
Input | Output |
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