83 lines
3.8 KiB
TeX
83 lines
3.8 KiB
TeX
\documentclass{maratona}
|
|
|
|
\begin{document}
|
|
\begin{ProblemaAutor}{}{Conversor Fonético Genérico}{1}{256}{Leetcode 127}
|
|
|
|
|
|
|
|
Nos laboratórios secretos de linguística computacional do \textbf{Instituto de Filologia Binária (IFB)}, um grupo de pesquisadores (e estagiários desesperados) finalmente concluiu o desenvolvimento do \textit{Conversor Fonético Genérico} (CFG). Este dispositivo revolucionário, que mais parece uma torradeira antiga com fios coloridos, é capaz de transmutar uma palavra em outra por meio de "mutações linguísticas controladas".
|
|
|
|
O CFG, no entanto, opera sob regras quânticas muito estritas:
|
|
|
|
\begin{enumerate}
|
|
\item \textbf{Mutação Única:} Em cada etapa da transformação, \textbf{apenas uma letra} da palavra atual pode ser alterada para uma nova letra.
|
|
\item \textbf{Validação de Realidade:} A nova palavra gerada pela mutação deve ser "real", ou seja, ela \textbf{deve existir} no vasto (e um tanto pedante) dicionário interno da máquina.
|
|
\end{enumerate}
|
|
|
|
Se uma mutação gerar uma palavra que não está no dicionário (um "blabismo vocabular"), a transformação é rejeitada, o fusível principal do CFG queima, e o processo falha catastroficamente.
|
|
|
|
Os pesquisadores querem agora otimizar o processo. Eles não querem qualquer transformação; eles precisam encontrar a \textbf{sequência de transformação mais eficiente} — aquela que usa o menor número possível de palavras para ir da palavra inicial até a palavra final.
|
|
|
|
|
|
Dadas duas palavras, \texttt{inicio} e \texttt{fim} (ambas com o mesmo comprimento), e um dicionário de palavras válidas, determine o \textbf{menor número de palavras} na sequência de transformação que converte \texttt{inicio} em \texttt{fim}, obedecendo às regras de mutação do CFG.
|
|
|
|
Note que todas as palavras intermediárias na sequência, bem como a palavra \texttt{fim}, devem existir no dicionário. A palavra \texttt{inicio} não precisa estar no dicionário (ela é o ponto de partida).
|
|
|
|
Se não for possível realizar a transformação, o CFG deve retornar $0$.
|
|
|
|
\Entrada
|
|
|
|
A entrada começa com dois inteiros $n$ e $m$, onde $n$ é o número de palavras disponíveis no dicionário ($1 \leq n \leq 5000$) e
|
|
$m$ o comprimento de cada palavra ($1 \leq m \leq 10$).
|
|
|
|
Na segunda linha há duas palavras: \texttt{inicio} e \texttt{fim}, ambas contendo exatamente $m$ letras minúsculas do alfabeto.
|
|
|
|
Após isso, seguem $n$ linhas, cada uma contendo uma palavra de $m$ letras minúsculas, representando as palavras do dicionário interno do CFG.
|
|
Todas as palavras do dicionário são únicas.
|
|
|
|
\Saida
|
|
|
|
A saída consiste em um único número inteiro: o comprimento da menor sequência de transformação que converte a palavra \texttt{inicio} na palavra \texttt{fim}, seguindo as regras do CFG.
|
|
|
|
Se não for possível realizar a transformação, o programa deve imprimir $0$.
|
|
|
|
\ExemploEntrada
|
|
\begin{Exemplo}
|
|
\texttt{6~3} & \texttt{4}\\
|
|
\texttt{mao~sol} & \\
|
|
\texttt{cao} & \\
|
|
\texttt{sal} & \\
|
|
\texttt{sao} & \\
|
|
\texttt{sai} & \\
|
|
\texttt{mel} & \\
|
|
\texttt{sol} & \\
|
|
\rowcolor{gray!20}\texttt{7~4} & \texttt{0}\\
|
|
\rowcolor{gray!20}\texttt{lata~fogo} & \\
|
|
\rowcolor{gray!20}\texttt{lido} & \\
|
|
\rowcolor{gray!20}\texttt{lapa} & \\
|
|
\rowcolor{gray!20}\texttt{lava} & \\
|
|
\rowcolor{gray!20}\texttt{fava} & \\
|
|
\rowcolor{gray!20}\texttt{fogo} & \\
|
|
\rowcolor{gray!20}\texttt{lago} & \\
|
|
\rowcolor{gray!20}\texttt{logo} & \\
|
|
\end{Exemplo}
|
|
|
|
|
|
|
|
\Notas
|
|
|
|
|
|
Caso de Teste 1:
|
|
Neste caso, queremos transformar "mao" em "sol".
|
|
|
|
O dicionário contém palavras intermediárias que permitem mutações válidas alterando apenas uma letra por vez.
|
|
Uma possível sequência mínima é:
|
|
|
|
mao → sao → sal → sol
|
|
|
|
A sequência tem 4 palavras no total.
|
|
|
|
Caso de Teste 2:
|
|
Não é possível converter "lata" em "fogo", portanto a resposta é 0.\end{ProblemaAutor}
|
|
\end{document}
|