Este problema consiste em contar o número de caminhos para chegar iniciando até parte inferior direita em uma matriz MxN realizando no máximo k curvas como mostrado na figura.O que é uma curva?
Cada movimento que altera a direção é considerado uma curva, isto é,
- se nós estávamos nos movendo ao longo da linha e passamos a nos mover ao longo da coluna
- ou se estávamos nos movendo ao longo da coluna e agora passamos a mover ao longo da linha.
Podemos resolver este problema em tempo polinomial, utilizando uma matriz multidimensional com 4 dimensões para guardar a quantidade de caminho nas células considerando a quantidade de curvas e mudanças de direção.
O vídeo mostra como implementar a solução deste problema.
Nenhum comentário:
Postar um comentário