Pathword Quest
Dir wird ein
n x n Gitter aus kleinbuchstabigen englischen Buchstaben gegeben. Deine Aufgabe besteht darin herauszufinden, ob es in diesem Gitter einen einfachen Pfad gibt, der in der richtigen Reihenfolge den String s bildet.💡
Ein einfacher Pfad beginnt in einer beliebigen Zelle des Gitters und bewegt sich bei jedem Schritt in eine benachbarte Zelle (nach oben, unten, links oder rechts).
Der Pfad darf jede Zelle nur einmal besuchen und kann dabei die Richtung beliebig ändern.
Die Buchstaben auf dem Pfad müssen beim Lesen der Reihe nach den String
s ergeben.Eingabe
Die erste Zeile enthält eine ganze Zahl
n (1 ≤ n ≤ 6), die die Größe des Gitters angibt.Die nächsten
n Zeilen enthalten jeweils n kleinbuchstabige englische Buchstaben, die die Buchstaben in den Zellen des Gitters repräsentieren.Die letzte Zeile enthält den String
s (1 ≤ |s| ≤ 15), bestehend aus kleinbuchstabigen englischen Buchstaben.Ausgabe
Gib
YES aus, wenn ein einfacher Pfad existiert, der in der richtigen Reihenfolge den String s bildet. Andernfalls gib NO aus.Beispiele
Eingabe | Ausgabe |
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