|
Количество маршрутов
(Время: 1 сек. Память: 32 Мб Сложность: 42%)
Квадрат разлинован на N×N клеток. Исполнитель робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Робот не может выходить за пределы квадрата. В каждой клетке квадрата записано одно из двух чисел: 0 или 1. Если в клетке записано число 1, робот может попасть в эту клетку, а если в клетке записано число 0, то робот не может попасть в такую клетку.
Требуется определить количество способов, которыми Робот может попасть из левой верхней клетки в правую нижнюю. Гарантируется, что в стартовой и конечной клетках стоит 1.
Входные данные
Входной файл INPUT.TXT содержит таблицу N×N, состоящую из N строк, в каждой строке записано N целых чисел Aij (0 ≤ Aij ≤ 1), разделенных символом «;» (точка с запятой). (2 ≤ N ≤ 20).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1;1;0
1;1;1
0;1;1 | 4 |
| 2 |
1;1;1;1;0;1;0;0;0;1;0;0;1;1;1
1;1;1;1;0;1;1;1;1;1;1;0;1;1;1
1;1;1;1;0;1;1;1;0;1;0;0;1;1;0
1;1;1;1;1;1;1;0;1;0;1;1;1;1;1
1;1;1;1;1;1;1;1;1;1;0;1;0;1;1
1;1;1;1;1;0;1;0;1;1;1;0;1;1;0
1;1;1;0;0;0;1;1;1;1;1;0;1;1;1
1;1;1;1;1;1;1;1;1;1;0;1;1;1;1
1;1;1;1;1;1;1;0;1;1;1;1;0;0;1
1;1;1;1;1;1;1;0;1;0;1;1;1;1;1
1;1;1;1;1;0;1;0;1;1;1;1;1;1;0
1;1;1;1;1;1;1;1;1;1;1;0;1;1;1
0;1;0;1;0;1;1;1;0;1;1;1;1;1;0
1;1;1;1;0;0;1;0;1;0;0;1;1;1;1
1;1;1;1;1;1;1;1;0;1;1;1;1;1;1 | 118410 |
Пояснение к примеру №1
Всего существует 4 маршрута робота:
- вправо, вниз, вправо, вниз;
- вправо, вниз, вниз, вправо;
- вниз, вправо, вправо, вниз;
- вниз, вправо, вниз, вправо.
Пояснение к примеру №2
Файл с заданием в формате Excel: 18.xlsx .
Файл с решением в формате Excel: 18_solution.xlsx .
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
