Годинник | |
|
Maxsum
|
Задача Maxsum
Журі думає, що вам доводилося розв’язувати таку задачу:
«Є прямокутна таблиця розміром M рядків на N стовпців. У кожній клітинці записано ціле число. По ній потрібно пройти згори вниз, починаючи з якої-небудь клітинки верхнього рядка, далі кожного разу переходячи в одну з «нижньо-сусідніх» клітинок (іншими словами, з клітинки з номером (i, j) можна перейти або на (i+1, j-1), або на (i+1, j), або на (i+1, j+1); в разі j=N можливі лише 1-й і 2-й з трьох перерахованих варіантів, в разі j=1 - лише 2-й і 3-й) і закінчити маршрут в якій-небудь клітинці нижнього рядка.
Напишіть програму, яка знаходитиме максимально можливу суму значень пройдених клітинок серед усіх допустимих шляхів»
Розв’яжіть дану задачу при додатковому обмеженні: допускаються лише шляхи, які проходять (хоча б по одному
разу) через всі стовпчики.
Технічні умови
Программа Maxsum читає з клавіатури M і N - кількість рядків і кількість стовпців (2<= M<= 200, 2<= N<= 40, M>=N), далі в кожному з подальших M рядків зчитується рівно по N розділених пропусками цілих чисел (кожне не перевищує по модулю 1000000) - значення клітинок таблиці. Програма виводить на екран єдине число- шукану величину.
Приклад
Введення
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Виведення
28 |
|
|
