Somme maximale d’un chemin de chute
Étant donné une grille de hauteur
h et de largeur w, vous devez déterminer la somme la plus élevée que l’on puisse obtenir en se déplaçant de haut en bas. À chaque étape, il n’est possible de se rendre que vers l’une des trois cellules adjacentes situées directement en dessous. Autrement dit, depuis la position (r, c), on peut se déplacer vers (r + 1, c - 1), (r + 1, c) ou (r + 1, c + 1). On parle de « somme de chute » parce qu’on « tombe » du sommet de la grille jusqu’au bas. Trouvez la somme maximale possible sur un tel chemin.ㅤ | o | ㅤ | ㅤ |
↙️ | ⬇️ | ↘️ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
Entrée
La première ligne de l’entrée contient deux nombres entiers
h et w (1 ≤ h, w ≤ 100).Les
h lignes suivantes contiennent w valeurs (-100 ≤ ≤ 100) représentant les valeurs de la grille à la ligne r et à la colonne c.Sortie
Le programme doit afficher la somme maximale possible parmi tous les chemins de chute envisageables.
Exemples
Entrée | Sortie |
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