C Algoritmo para procurar uma saida

Arkcanjou · 4 de outubro de 2021

Preciso de uma luz com um algoritmo que dada um labirinto encontre o menor caminho possivel até a saida

O que eu fiz até o momento é que a partir do ponto de inicio o codigo vai definindo um valor de "peso" para cada movimento até que ele encontre a saida e isso tudo fica em uma matriz.

Usando essa matriz de exemplo como eu poderia encontrar o menor caminho até o valor 99

#  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #
#  #  #  #  #  14 13 12 11 10 9  8  7  6  5  4  3  #
#  #  #  #  #  #  14 13 12 11 10 9  8  #  4  3  2  #
#  #  #  #  #  #  15 14 13 12 11 10 9  #  3  2  1  #
#  #  #  #  #  #  #  15 14 13 #  11 10 11 #  1  0  #
#  #  #  #  #  #  #  #  99 #  #  #  #  #   #  #  # #

No lugar das cerquilhas são valores que representam posiçoes invalidas troquei apenas para ficar melhor para visualizar

arfneto · 4 de outubro de 2021

Se você não tem uma sólida formação em matemática sugiro tentar estudar alguns dos algoritmos clássicos desse tipo, antes de programar algo.

58 minutos atrás, Inutilzao disse:

O que eu fiz até o momento é que a partir do ponto de inicio o codigo vai definindo um valor de "peso" para cada movimento até que ele encontre a saida e isso tudo fica em uma matriz

Acho que é uma ideia muito boa! Nesse caso o peso deve ser 1 porque todos os caminhos tem o mesmo custo: a distância.

Tente algo em torno de matriz de adjacência, a representação comum disso que está escrevendo, e o algoritmo de Dijkatra, que acho que são conceitos mais simples de entender. Nesse tópico pode ter algo que ajude você a escrever algo: