Maximale fallende Pfadsumme
Gegeben ist ein Raster der Höhe
h und der Breite w. Ziel ist es, die maximale Summe zu bestimmen, die sich erreichen lässt, wenn man von der obersten bis zur untersten Zeile „fällt“. Bei jedem Schritt darf man sich nur in eines der drei benachbarten Felder direkt darunter bewegen. Befindet man sich also an der Position (r, c), kann man zu diesen Positionen wechseln: (r + 1, c - 1), (r + 1, c) oder (r + 1, c + 1). Daher spricht man von einer „fallenden“ Summe – sie erstreckt sich von ganz oben bis ganz unten im Raster. Bestimmen Sie die maximale Summe eines solchen Pfads.ㅤ | o | ㅤ | ㅤ |
↙️ | ⬇️ | ↘️ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
h und w (1 ≤ h, w ≤ 100).Die nächsten
h Zeilen enthalten w Zahlen (-100 ≤ ≤ 100), die die Werte im Raster an Zeile r und Spalte c angeben.Ausgabe
Das Programm soll die maximal mögliche Summe ausgeben, die sich unter allen möglichen fallenden Pfaden erzielen lässt.
Beispiele
Eingabe | Ausgabe |
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