Здравствуйте. Долго сижу над задачей, помогите решить.
Есть поле из клеточек, в каждой клеточке записано целое (возможно, отрицательное) число.
На вход подаются 2 целых числа, больших нуля и не превышающих 1100: n и m, – размеры поля. После них в n строках задано по m чисел, – число в i-й строке и j-м столбце символизирует число, которое находится в клетке поля с индексами i и j.
При нумерации индексов с 1, мы начинаем игру в клетке (1;1), то есть в верхнем левом углу поля. За один ход мы можем либо походить вниз (если есть куда), либо походить вправо (если есть куда). Игра заканчивается в том и только том случае, когда мы доходим до клетки (n; m), то есть до самой нижней правой клетки поля.
В начале игры, когда мы еще не попали на поле, мы запоминаем число 0. Далее каждый раз, когда мы попадаем в новую клетку поля, мы к запомненному числу прибавляем то, которое находилось в этой клетке. То есть если в (1;1) стояло число 5, а в следующей клетке, в которую мы пошли (например, если мы пошли в (1;2), то в ней), стоит 10, то при попадании в (1;1) мы запомним уже число 5 (0+5=5), а при попадании в следующую клетку (при условии, что это всё та же (1;2)) – 15 (5+10=15).
Программа должна вывести одно единственное число – максимальное число, которое может быть запомнено у нас в голове к концу игры.
Ко всему этому идёт пару тестов.
2 3 1 2 3 4 5 6 Ответ: 16 2 3 1 2 2 1 1 1 Ответ: 6 4 4 1 8 2 2 7 4 6 5 0 0 0 0 3 4 3 4 Ответ: 28 10 10 1 8 4 6 20 3 9 8 54 7 54 2 8 3 7 9 10 41 5 16 0 0 37 6 41 56 81 29 93 4 83 12 34 60 0 0 54 7 2 1 2 4 6 8 10 12 14 16 18 20 20 18 16 14 12 10 8 6 4 2 7 9 4 2 10 20 30 41 31 21 40 30 20 10 40 30 20 10 0 0 -10 -20 -30 -40 -50 -60 -70 -80 -90 -100 -100 -90 -80 -70 -60 -50 -40 -30 -20 -10 Ответ: 375 
