Pathword Quest
Você recebe uma grade de tamanho
n x n composta por letras minúsculas do alfabeto inglês. Sua tarefa é verificar se existe um caminho simples nessa grade que possa ser lido como a string s fornecida.💡
Um caminho simples começa em qualquer célula da grade e avança para uma célula adjacente (para cima, para baixo, para a esquerda ou para a direita) em cada passo.
Esse caminho só pode visitar cada célula uma vez e pode mudar de direção conforme necessário.
As letras encontradas ao longo do caminho devem formar a string
s na ordem correta.Entrada
A primeira linha contém um inteiro
n (1 ≤ n ≤ 6), que representa o tamanho da grade.As próximas
n linhas contêm n letras minúsculas do alfabeto inglês cada, representando as letras de cada célula da grade.A última linha contém a string
s (1 ≤ |s| ≤ 15), composta por letras minúsculas do alfabeto inglês.Saída
Imprima
YES se existir um caminho simples na grade que forme a string s ao ler as letras em sequência. Caso contrário, imprima NO.Exemplos
Entrada | Saída |
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