Максимальная сумма падающего пути
Дана сетка высотой
h и шириной w. Нужно вычислить максимальную сумму, которую можно набрать, перемещаясь сверху вниз, причём на каждом шаге разрешено переходить только в одну из трёх соседних ячеек следующей строки. Иными словами, находясь в позиции (r, c), можно перейти в (r + 1, c - 1), (r + 1, c), или (r + 1, c + 1). Именно поэтому мы называем эту сумму «падающей»: мы «падаем» с верхней части сетки до самого низа. Определите, какова максимальная сумма такого пути.ㅤ | o | ㅤ | ㅤ |
↙️ | ⬇️ | ↘️ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
Входные данные
Первая строка содержит два целых числа
h и w (1 ≤ h, w ≤ 100).Следующие
h строк содержат по w чисел (-100 ≤ ≤ 100), которые задают значения в сетке для строки r и столбца c.Выходные данные
Программа должна вывести максимально возможную сумму, которую можно получить среди всех допустимых падающих путей.
Примеры
Входные данные | Выходные данные |
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