№445880387

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из команд: вправо или вниз. Робот начинает движение в левой верхней клетке квадрата. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Числа в клетках в этом задании значения не имеют.

Клетки, которые справа и снизу ограничены стенами, назовём конечными: в них Робот останавливается.

Определите общее количество различных маршрутов Робота из начальной клетки в какую-нибудь конечную клетку.

Исходные данные представляют собой электронную таблицу размером N × N (в файле N = 21), каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.