Pathword Quest
You are given an
n x n grid of lowercase English letters. Your task is to determine whether there is a simple path in this grid that can be read as the given string s.💡
A simple path starts from any cell in the grid and moves to an adjacent cell (up, down, left, or right) in each step.
The path can only visit each cell once and can change direction as needed.
The letters in the path must form the string
s when read in order.Input
The first line contains an integer
n (1 ≤ n ≤ 6), representing the size of the grid.The next
n lines contain n lowercase English letters each, representing the letters in each cell of the grid.The last line contains a string
s (1 ≤ |s| ≤ 15), consisting of lowercase English letters.Output
Print
YES if there is a simple path in the grid that forms the string s when read in order. Otherwise, print NO.Examples
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