#40 Exercício - Duende perdido

Nome: Duende perdido
Link: http://br.spoj.pl/problems/DUENDE/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.04
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 1

Comentário:
Já faz um tempo que eu tava de olho nesse problema, hoje eu descobri a saída.
Eu montei uma função recursiva, que pra minha surpresa deixou o algoritmo bem enxuto e objetivo.

Eu recomendo que pesquisem algo sobre o pathfinding.
Existem algum tipos de pathfinding, e eu não tenho certeza se algum deles se aplicam neste exercício.
Acontece que existem os pathfindings "gulosos", que escolhem o melhor caminho no momento e vão seguindo. Acontece que esse melhor caminho no momento, pode ser o caminho errado se olhado de uma maneira geral. Digamos que o atalho as vezes não valha a pena. Então esse algoritmo guloso traria a resposta errada, visto que ele só verifica este caminho.
Já um algoritmo não guloso verificaria todos os caminhos, sem excessão, e portanto trará a resposta certa (se implementado corretamente).

Pesquisem e identifiquem se o algoritmo é guloso ou não. Eu não tenho certeza, pode ser que o guloso por sorte encontre sempre o caminho correto nos casos de teste do spoj. Vocês é que sabem.

Este exercício pode também ser resolvido com uma BFS (breadth first search), que foi o que eu escolhi.

Dica:
- Pesquisem pathfinding, e BFS.
- Pensem numa maneira de mapear a matriz com pontos de distância.
- Tomem cuidado com as casas já visitadas, e também prestem atenção nelas, pode haver um jeito mais econômico de chegar nelas.

Casos de teste úteis


Entrada:
3 3
0 1 1
1 2 1
3 1 1

3 3
1 1 1
1 2 1
3 1 0

6 9
0 1 2 1 0 1 2 1 0
1 2 1 1 1 1 2 1 1
1 1 2 1 1 1 1 1 1
2 2 2 1 1 2 2 2 2
3 1 2 2 1 1 1 1 1
1 1 1 1 1 2 1 1 1

Saída:
2
2
10