Центр индивидуальной подготовки
школьников и студентов
40-33-54

ЗАДАНИЕ 18 - 105

Квадрат разлинован на N×N клеток (1 <, N <, 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю вверх. При попытке выхода за границу квадрата Робот разрушается, при столкновении со стеной робот разрушается. В каждой клетке записано число – количество монет, которое необходимо заплатить за проход. Если число отрицательное – счёт робота уменьшается, если положительное – увеличивается.

Определите максимальное значение счета робота, если:

- роботу запрещено перемещаться при отрицательном счёте,

- робот может перемещаться при отрицательном счёте.


Начальным значением счёта является значение стартовой клетки. Стартовая клетка - левая нижняя.


Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.