Problema E - Tile Game

Autor: André Restivo (Fac. de Engenharia da Universidade do Porto)
Tipo de problema: Pesquisa em Largura
Número de ficheiros de teste: 19

Este é um dos problemas mais clássicos de concursos. Um puzzle, onde um estado inicial de um tabuleiro e uma série de movimentos que temos de usar até chegar ao estado final. Neste caso, o que é pedido é o mais usual: o menor número de movimentos necessário para chegar de um estado ao outro.

O método óbvio para resolver este problema é a pesquisa em largura. Desde modo, quando chegamos a um estado, garantidamente chegamos no menor número de movimentos possíveis. Algumas coisas a ter em conta:

• Como imprimir o caminho lexicograficamente menor? Basta expandir a pesquisa por ordem dos movimentos!

• Temos de ter maneira de saber se um estado já foi atingido para não voltarmos a ele. Como fazê-lo? Há muitas maneiras, mas recorda que apenas existem no máximo 512 (2^9) diferentes estados!

• Ter o cuidado de mal colocamos um estado no final da fila o marcar como visitado, e não apenas ao retirá-lo do início da fila. Caso contrário, teremos um crescimento exponencial no número de estados a visitar, em vez do máximo desejável de apenas 512.

Ligações interessantes:

• Pesquisa em Largura na Wikipedia