33 lines
2.8 KiB
TeX
33 lines
2.8 KiB
TeX
O problema de transformação de palavras exige encontrar o menor caminho entre uma palavra inicial e uma palavra final, alterando apenas uma letra por vez, com a restrição de que todas as palavras intermediárias devem pertencer a um dicionário fornecido.
|
|
|
|
\subsection*{Representação do estado}
|
|
|
|
\begin{itemize}
|
|
\item Cada palavra do dicionário (incluindo a palavra inicial) representa um nó em um grafo não direcionado.
|
|
\item Uma aresta conecta duas palavras se elas diferem em exatamente uma letra, uma "mutação" válida.
|
|
\item A transformação mais eficiente equivale a encontrar o caminho mais curto entre o nó inicial e o nó final neste grafo.
|
|
\end{itemize}
|
|
|
|
\subsection*{Estratégia de solução usando BFS (Busca em Largura)}
|
|
|
|
Como precisamos encontrar o menor número de passos em um grafo com arestas de peso uniforme e não direcionadas, a Busca em Largura (BFS) é a abordagem algorítmica ideal.
|
|
|
|
\begin{enumerate}
|
|
\item Leia o número de palavras no dicionário ($N$) e o comprimento das palavras ($M$), seguidos das palavras inicial e final.
|
|
\item Armazene todas as palavras do dicionário em um conjunto (\textit{hash set}) para buscas eficientes. Insira também a palavra inicial neste conjunto, pois ela é o nosso ponto de partida.
|
|
\item Construa o grafo através de uma lista de adjacências:
|
|
\begin{itemize}
|
|
\item Para cada palavra no conjunto, itere sobre cada um de seus $M$ caracteres.
|
|
\item Substitua o caractere atual temporariamente por todas as 26 letras minúsculas do alfabeto ('a' a 'z').
|
|
\item Se a nova palavra gerada após essa substituição também existir no dicionário, adicione-a à lista de adjacências da palavra original.
|
|
\end{itemize}
|
|
\item Inicialize a simulação da BFS: crie uma fila e insira a palavra inicial. Utilize um conjunto auxiliar para registrar os nós já visitados (\texttt{seen}), evitando ciclos infinitos. Defina a distância (profundidade) inicial da sequência como $1$.
|
|
\item Processe a fila operando por camadas (nível por nível):
|
|
\begin{itemize}
|
|
\item Descubra quantos elementos existem na fila atual. Este é o número de palavras no nível de profundidade atual.
|
|
\item Para cada uma dessas palavras, retire-a da fila e verifique: se for a palavra final desejada, a missão foi concluída! Imprima a profundidade atual e encerre.
|
|
\item Caso contrário, acesse a lista de adjacência da palavra. Para cada vizinho (mutação válida) que ainda não foi visitado, insira-o na fila e marque-o como visitado.
|
|
\end{itemize}
|
|
\item Ao terminar de processar todas as palavras da camada atual, incremente a profundidade.
|
|
\item Se a fila se esvaziar completamente e a palavra final nunca for atingida, a transformação é impossível sob essas regras. Retorne $0$.
|
|
\end{enumerate} |