Dada a imagem abaixo, preciso detectar a sequência mais ideal no quadro (a linha verde). As linhas azul / vermelha representam possíveis, mas não os melhores movimentos.
Aqui estão as regras:
- Você pode mover para qualquer bloco que seja o mesmo e seja seu vizinho (a diagonal é válida)
- Depois de visitar um bloco, você não poderá visitá-lo novamente.
Eu pensei em percorrer cada nó, e olhar para os vizinhos, depois percorrer recursivamente. Depois de encontrar um possível movimento, posso colocá-lo em uma estrutura. Depois que todos os movimentos possíveis são encontrados, basta escolher o movimento com a maior contagem de nós. Torna-se mais difícil quando um nó tem mais de um vizinho que corresponde.
Então, existe algum algoritmo que eu possa usar? Eu estava pensando em algum tipo de inundação, mas isso não atende às regras # 2.
Conforme solicitado, aqui está um vídeo de jogabilidade semelhante. http://youtube.com/watch?v=eumnCTG0AE8
Respostas:
Você pode considerar cada grupo de símbolos idênticos vinculados (e vinculado, quero dizer, que você pode viajar de um símbolo para outro) como um gráfico separado . Para cada gráfico, aplique uma DFS ( Depth First Search ) começando em cada nó no gráfico que ainda não faz parte do caminho mais longo para esse gráfico . Sempre que você atingir um beco sem saída ao aplicar um DFS, verifique se o caminho que você acabou de percorrer é maior que o máximo global que você encontrou até agora. Se estiver, armazene-o como o novo caminho mais longo.
Você notará que no parágrafo anterior mencionei a aplicação de um DFS várias vezes para cada gráfico. Um único DFS executado em um gráfico não seria suficiente. Considere este caso em particular:
Se por acaso você executasse primeiro um DFS neste gráfico no nó superior, descobriria o caminho mais longo possível como sendo a linha vertical, mas isso não estaria correto. Isso aconteceria sempre que você iniciar o algoritmo DFS em um nó que esteja em algum lugar dentro do caminho resultante ou que não faça parte dele. O que você precisa fazer neste exemplo específico também é iniciar um algoritmo DFS a partir do nó mais à esquerda na segunda linha. Isso encontrará o caminho correto. De um modo geral, você precisará executar algoritmos DFS em cada nó que atualmente não faz parte do caminho mais longo para esse gráfico, conforme declarado acima.
O pior cenário absoluto para esse algoritmo seria um tabuleiro preenchido ou preenchido principalmente com um único tipo de símbolo, porém é improvável que isso aconteça no jogo. Além disso, tenha cuidado ao armazenar os caminhos mais longos para cada gráfico. Se você não otimizar esse bit, é melhor chamar um DFS para cada nó no palco. Supondo que você não trabalhe com placas muito grandes e que a velocidade não seja um problema, essa solução deve ser rápida o suficiente.
Tecnicamente falando, ao dividir sua placa em gráficos separados, você acaba com vários " Problemas do caminho mais longo ". Como podemos ver no seu exemplo, você pode ter ciclos em seu gráfico (por exemplo, tendo todos os símbolos do lado de fora do palco do mesmo tipo), o que significa que nesse problema em particular você precisa encontrar o caminho mais longo em vários gráficos cíclicos não direcionados, o que não pode ser feito em tempo polinomial .
Se você achar que isso é muito lento, consulte esta resposta no StackOverflow para obter mais detalhes sobre como otimizar os "Problemas de Caminho Mais Longo" individuais.
fonte