Oi Rafael,
Eu não sei como resolver esse e consegui pensar apenas um pouco nele.
Na sua versão memoizada, você guardou a posição da cobra inteira? Acho que dá para guardar apenas o início e fim da cobra. Apenas isso afeta o número de passos,
e aí para decidir se você pode ir de uma posição a outra, você tem que elaborar um pouco mais, vendo se há um jeito da cobra estar com a cabeça e o rabo nos lugares especificados para que haja um tal caminho. Deu para entender? Será que isso ajuda a tornar o seu algoritmo mais rápido?
A sua BFS faz a cobra se mover um passinho de cada vez? Se você controlar a posição da cabeça e do rabo dela (em vez da posição dela toda), acho que pode ir direto de uma maça (ovo, não?) para a próxima, e aí tentar usar um esquema mais na linha do Dijkstra, expandindo primeiro os ramos mais promissores.
Não sei se ajudou muito... Me mande o seu código para eu dar uma olhada...
Cris
Fórum