Matriz 5x5, caminho mais curto entre os pontos A e B

[Emanuel Huber 0]

Eai pessoal, hoje em minha aula de Lógica Computacional meu prof conseguiu fazer minha cabeça explodir com o seguinte exercício:

Labirinto:
Ajude seu personagem a chegar ao ponto 3 pelo caminho mais curto, seu algoritmo deve ler uma matriz 5x5 onde o usuário dá como entrada posição inicial do personagem, onde ele deve chegar e os obstáculos no caminho, seu programa deve mostrar as coordenadas que o personagem deve seguir para chegar no final pelo caminho mais curto.

Exemplo de Matriz de Entrada:

1 - Obstáculo
2 - Início
3 - Fim
0 - Caminho livre

0 0 1 0 1
1 2 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 3

Obs: o personagem só pode andar pelo caminho livre, e sempre considere que a entrada sempre tenha solução.


Então pessoal, quebrei muito a minha cabeça com isso, mas ainda não consegui encontrar uma maneira eficiente de encontrar o caminho mais curto.
Já pensei em fazer por força bruta, analisando cada zero vizinho do 2 e por ai continuar as verificações de zeros vizinhos até chegar no 3, porém o problema disso seria quando eu encontrasse bifurcações no caminho, ou quando a matriz está completamente zerada(sem obstáculos), não consegui pensar em nada.

Lembrando que não estou pedindo um código pronto, só estou pedindo uma ajuda na lógica do problema, algo que não enxerguei que pode ser feito para solucioná-lo, agradeço a todos

[KhaosDoctor 242]

A unica maneira de você verificar o caminho mais curto é fazendo todos os caminhos possíveis. Você pode substituir os lugares aonde você já passou por um "X", se houver bifurcações você deve ter um código capaz de entender que aquilo é uma bifurcação e ai fazer o programa tomar ambos os caminhos para verificar qual deles é o menor.

[_Isis_ 202]

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://en.wikipedia.org/wiki/A*_search_algorithm