Задание из городской олимпиады по информатике
Задача 2 “Їжак”.(20 балів)
План прямокутного саду розміром m*n складається з квадратних зон. У кожній зоні росте по дереву. З кожного дерева будь якої зони можуть упасти кілька яблук.
У лівому верхнбому квадратику знаходиться їжак, який повинен дійти до правого нижнього квадратика. В саду існують обмеження відносно способу переміщення: їжак може рухатися із поточного квадратика тільки один із двох сусідніх правий або нижній.
Складіть програму яка знаходить максимальну кількість яблук, яку може зібрати їжак, рухаючись у напрямі потрібного квадратика.
Технічні вимоги:
Вхідний файл: EG.IN
Вихідний файл: EG.OUT
План саду заданий таблицею apples, яка містить m рядків та т стовпчиків. Елемент apples[i,j] таблиці вказує на кількість яблук які впали з дерева в зону з координатами i,j.
Формат вхідних даних:
Перший рядок містить два числа m та n, вказаних через пропуск: перше число – кількість рядків, друге – кількість стовпчиків у таблиці.
У кожному із наступних m рядків міститься по n чисел, вказаних через пробіл.
Формат вихідних даних:
Один рядок – натуральне число.
Приклад файлів вхідних та вихідних даних:
EG.IN
3 3
1 2 3
1 2 3
1 2 3
EG.OUT
12
|