Soma máxima de caminho descendente
Dada uma grelha com altura
h e largura w, és desafiado a calcular a soma máxima que se pode obter ao deslocares-te de cima para baixo, onde em cada passo só é permitido mover-te para as 3 células adjacentes que ficam imediatamente abaixo. Ou seja, estando na posição (r, c), podes mover-te para as posições: (r + 1, c - 1), (r + 1, c), e (r + 1, c + 1). Chamamos a isto a soma de queda, pois “caímos” desde o topo até à última linha da grelha. Encontra a soma máxima ao longo desse caminho.ㅤ | o | ㅤ | ㅤ |
↙️ | ⬇️ | ↘️ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
Entrada
A primeira linha da entrada contém dois inteiros
h e w (1 ≤ h, w ≤ 100).As seguintes
h linhas contêm w números (-100 ≤ ≤ 100) que representam os valores da grelha na linha r e na coluna c.Saída
O programa deve imprimir a maior soma que se pode obter dentre todos os possíveis caminhos de queda.
Exemplos
Entrada | Saída |
3 3
2 1 3
6 5 4
7 8 9 | 17 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB