Задание №18: Динамическое программирование (Робот в таблице)

(Информатик-БУ) Квадрат разлинован на N×N клеток (1 < N < 12). Исполнитель Змейка может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Змейка перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенками, сквозь стену Змейка пройти не может. В некоторых клетках квадрата расположены двоичные цифры (0 или 1). Посетив клетку с цифрой, Змейка подставляет её к своей голове. Например, посетив клетку с единицей, Змейка вида «1011» превратится в «10111», а посетив клетку с нулём – в «10110». Определите максимальное и минимальное значение Змейки после того, как она пройдет из левой верхней клетки в правую нижнюю.
Исходные данные записаны в файле 18-147.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальное значение, затем минимальное. Ответы запишите в десятичной системе счисления.