Задача:Только вправо или вниз С++

[Blugu]

Игровое поле N×M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо шага игрок покидает пределы поля, такой шаг запрещается.
Требуется написать программу, которая определит число различных вариантов путей от верхнего левого угла до правого нижнего (и их отображения). Результаты располагать в порядке увеличения шагов. А также найти такой путь из клетки старта в клетку финиша, чтобы сумма цифр в клетках, через которые он пролегает, была минимальной.
Входные данные: размеры поля N (1 ≤ N ≤ 70) и M (1 ≤ M ≤ 70). N строк, каждая из которых описывает отдельную строку игрового поля, записанные через пробел по M целых чисел - длины шагов из клеток данной строки.

[Valick]

Длина шага (цифра в клетке) чем-то ограничена?
В правый нижний угол я так понимаю вход без разницы какой лины шаг?

[Blugu]

Длина шага не ограничена.
В правый нижний угол я так понимаю вход без разницы какой длины шаг? да без разницы.

[Valick]

Сообщение от Blugu

Длина шага не ограничена.

Так не интересно, я бы всё таки ограниил шаг в клетке рандомным числом от 1 до минимального из (N, M)
Например игровое поле 10х15, значит шаги от 1 до 10.
А то как-то записывать в клетку число с 30-тью нулями при размере поля 10 на 10 "не айс".

[Blugu]

В задаче четко про это не написано, поэтому я думаю можно и ограничить. Единственное шаг (число в клетке) может быть и 0. В примере вот такое поле изображено.

[Valick]

Blugu, ок. задача интересная, люблю такие. К сожалению очень мало свободного времени, но первое что приходит в голову. Это берём координату 0.0 с числом 2 (шаг 1) и проверяем шаг вправо (шаг 2) и шаг вниз (шаг 3), если оба шага доступны, то сохраняем эти шаги с информацией о том откуда сделан шаг (т.е. коордтната 0.0), повторяем этот алгоритм для каждого их сохранённых шагов, если же ход недоступен, то просто не сохраняем эту ветку. В итоге собираем в цепочки только те шаги которые достигли конца (от конца к началу).

[Blugu]

Найти и вывести количество все возможных путей в матрице, от верхнего левого угла до правого нижнего, двигаться можно только вправо или вниз.

[BDA]

Объединил темы, т.к. обсуждается практически одна и та же задача. Хотя количество путей и сами пути, это разные вещи. Прототип на питоне, который считает количество путей:

def paths(n, m):
    if n == 1 or m == 1:
        return 1
    return paths(n - 1, m) + paths(n, m - 1)

print(paths(10, 10))