Solução Caminho

Solução por Rogério Júnior

Para uma determinada leveza $$p$$, é fácil usarmos uma $$BFS$$ para descobrirmos se existe um caminho com essa leveza que leva da casa inicial à final, bem como definirmos o tamanho do menor dentre estes caminhos. Basta alterarmos o algoritmo comum da $$BFS$$ para que ela só visite células que tenham valor menor ou igual a $$p$$.

Desse modo, se testássemos todas as levezas, a primeira que possibilitasse chegar do início ao fim do tabuleiro seria a resposta correta, logo, basta fazermos uma busca binária para descobrirmos qual a menor leveza que funciona!

Se você não conhece a busca binária, clique aqui para ver esta aula no Curso Noic. Se você não conhece a $$BFS$$, clique aqui para ver esta aula no Curso Noic.

Segue o código para melhor entendimento:

https://gist.github.com/rogerioagjr/861effe429ddadf355f766d00a798fe2