Pathword Quest
Vi viene fornita una griglia
n x n di lettere minuscole inglesi. Il vostro compito è stabilire se esiste un percorso semplice all’interno di questa griglia che, letto nell’ordine corretto, corrisponda alla stringa s.💡
Un percorso semplice inizia da qualsiasi cella della griglia e si sposta, a ogni passo, in una cella adiacente (su, giù, sinistra o destra).
Il percorso può visitare ogni cella soltanto una volta e può cambiare direzione secondo necessità.
Le lettere presenti nel percorso devono formare la stringa
s quando vengono lette in sequenza.Input
La prima riga contiene un intero
n (1 ≤ n ≤ 6), che rappresenta la dimensione della griglia.Le successive
n righe contengono ciascuna n lettere minuscole inglesi, che rappresentano le lettere in ogni cella della griglia.L’ultima riga contiene una stringa
s (1 ≤ |s| ≤ 15), composta da lettere minuscole inglesi.Output
Stampate
YES se esiste un percorso semplice nella griglia che formi la stringa s nell’ordine corretto. Altrimenti, stampate NO.Esempi
Ingresso | Uscita |
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