Только вправо или вниз
(Время: 1 сек. Память: 16 Мб Сложность: 32%)
Игровое поле N×M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо шага игрок покидает пределы поля, такой шаг запрещается.
На рис. 1 приведен пример игрового поля 3×4, где сплошная окружность показывает положение начала, а пунктирная окружность – цель. Рис. 2 показывает три возможных пути от начала до цели для рассматриваемого примера игрового поля, с удаленными промежуточными числами.
Требуется написать программу, которая определит число различных вариантов путей от верхнего левого угла до правого нижнего.
Входные данные
Входной файл INPUT.TXT содержит в первой строке размеры поля N (1 ≤ N ≤ 70) и M (1 ≤ M ≤ 70). В последующих N строках входного файла, каждая из которых описывает отдельную строку игрового поля, записаны через пробел по M целых чисел от 0 до 100 – длины шагов из клеток данной строки.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число - число различных вариантов путей от верхнего левого угла до правого нижнего. Для каждого поля будет менее чем 231 различных путей.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 4
2 1 1 2
3 2 1 44
3 1 1 0
| 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
