Cris, alguma idéia para o Snake?
Como eu disse, eu tinha feito uma BFS memorizando os estados com um hash...
Ficou absurdamente lento por causa das possíveis formas da cobrinha.
Fiquei pensando se teria como ir mais direto para as maçãs, algo como Djikstra ou igual ao 15-puzzle, mas não tenho certeza se terei o melhor caminho...
Só 37 pessoas passaram e não tem nada no fórum...
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
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