Solução Caminho

0 Flares Facebook 0 0 Flares ×

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:

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: