Somma massima lungo il percorso di caduta
Data una griglia di altezza
h e larghezza w, ti viene richiesto di calcolare la somma massima ottenibile spostandoti dall’alto verso il basso, con la possibilità di muoverti a ogni passo solo in una delle tre celle adiacenti sottostanti. In altre parole, trovandoti in posizione (r, c), puoi passare alle posizioni: (r + 1, c - 1), (r + 1, c), oppure (r + 1, c + 1). È per questo che la definiamo una “falling sum” – perché si cade dall’estremità superiore della griglia fino al fondo. Individua la somma massima lungo il percorso.ㅤ | o | ㅤ | ㅤ |
↙️ | ⬇️ | ↘️ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
Dati di input
La prima riga dell’input contiene due interi
h e w (1 ≤ h, w ≤ 100).Le successive
h righe contengono w numeri (-100 ≤ ≤ 100), che rappresentano i valori nella griglia alla riga r e colonna c.Dati di output
Il programma deve stampare la somma massima possibile ottenuta fra tutti i percorsi di caduta possibili.
Esempi
Ingresso | Uscita |
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