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

Учитывая двумерную матрицу размера n*m , источник s и пункт назначения d , выведите количество всех уникальных путей от заданного s до d . Из каждой клетки можно двигаться либо только вправо , либо вниз .

Примеры :

Input: arr[][] = { {1, 2, 3}, {4, 5, 6} }, s = {0, 0}, d = {1, 2}
Output: 3
Explanation: All possible paths from source to destination are:

• 1 -> 4 -> 5 -> 6
• 1 -> 2 -> 5 -> 6
• 1 -> 2 -> 3 -> 6

Input: arr[][] = { {1, 2}, {3, 4} }, s = {0, 1}, d = {1, 1}
Output: 1

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

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(n+m)
Вспомогательное пространство : O(1)