Pathword Quest
Տրվում է
n x n չափի ցանց, որը պարունակում է փոքրատառ անգլերեն տառեր։ Ձեր նպատակն է պարզել, արդյոք գոյություն ունի ցանցում պարզ երթուղի, որը հերթականությամբ կարող է կարդալ տրված s տողը։💡
Պարզ երթուղին սկսվում է ցանցի ցանկացած վանդակից և յուրաքանչյուր քայլին անցնում է հարակից վանդակ (վեր, վար, ձախ կամ աջ)։
Երթուղին չի կարող մեկ վանդակ այցելել մեկից ավել անգամ, և անհրաժեշտության դեպքում թույլատրելի է փոխել ուղղությունը։
Երթուղու ընթացքում հանդիպող տառերը պետք է ձևավորեն
s տողը պատշաճ հերթականությամբ։Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ 6), որը նշում է ցանցի չափը։Հաջորդ
n տողերից յուրաքանչյուրում գրված է n փոքրատառ անգլերեն տառ՝ ցանցի վանդակների բովանդակությունը։Վերջին տողում տրված է
s (1 ≤ |s| ≤ 15) տողը, որն igualmente կազմված է փոքրատառ անգլերեն տառերից։Ելք
Եթե հնարավոր է գտնել պարզ երթուղի, որի տառերը հերթականությամբ տալիս են
s տողը, տպեք YES։ Հակառակ դեպքում տպեք NO։Օրինակներ
Մուտք | Ելք |
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