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

(А. Кабанов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке пересечь границы квадрата Робот разрушается. В каждой клетке квадрата записано одно из двух чисел: 0 или 1. Если в клетке записано число 1, Робот может попасть в эту клетку, а если в клетке записано число 0, то робот не может попасть в такую клетку. Определите количество способов, которыми Робот может попасть из левой верхней клетки в правую нижнюю. В ответе укажите искомое число.
Исходные данные для Робота записаны в файле 18-126.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.