Pathword Quest
Вам дана сетка размером
n x n, составленная из строчных английских букв. Ваша задача — выяснить, существует ли простой путь в этой сетке, который при чтении по порядку совпадает с заданной строкой s.💡
Простой путь может начинаться с любой ячейки сетки и на каждом шаге переходить в соседнюю ячейку (вверх, вниз, влево или вправо).
Каждую ячейку можно посетить только один раз, а направление может меняться по мере необходимости.
Символы пути должны образовывать строку
s при последовательном чтении.Входные данные
Первая строка содержит целое число
n (1 ≤ n ≤ 6), задающее размер сетки.Следующие
n строк содержат по n строчных английских букв, описывающих буквы в каждой ячейке сетки.Последняя строка содержит строку
s (1 ≤ |s| ≤ 15), состоящую из строчных английских букв.Выходные данные
Выведите
YES, если существует простой путь в сетке, который образует строку s при чтении по порядку. В противном случае выведите 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