Soma de caminho mínimo
Dada uma grelha de altura
h e largura w preenchida com números inteiros, pretende-se encontrar um percurso que vá do canto superior esquerdo ao canto inferior direito e que minimize a soma dos valores percorridos. Só é permitido mover para a direita ou para baixo.3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Entrada
A primeira linha da entrada contém dois inteiros
h e w (1 ≤ h, w ≤ 1000).As
h linhas seguintes contêm w inteiros separados por espaços, que representam os valores na grelha .Saída
O programa deve imprimir a soma mínima possível para chegar do canto superior esquerdo ao canto inferior direito.
Exemplos
Input | Output |
3 4
3 2 1 3
1 9 2 3
9 1 5 4 | 15 |
Explicação
Podemos deslocar-nos assim: 3 → 2 → 1 → 2 → 3 → 4
Hint 1
O estado num problema de programação dinâmica pode ser representado por um array bidimensional.
Hint 2
Esse array pode armazenar a melhor solução obtida até essa coordenada (ou seja,
d[r][c] representa o melhor percurso para chegar à linha r e à coluna c).Porque é que a abordagem gulosa (greedy) não funciona aqui? Se avançasses sempre na direção do menor valor imediato, que tipo de problema poderias encontrar?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB