Распечатайте все уникальные пути от заданного источника к месту назначения в матрице, двигаясь только вниз или вправо
Учитывая двумерный массив mat[][] , источник ' s ' и пункт назначения ' d ', вывести все уникальные пути от данного ' s ' до ' d '. Из каждой клетки можно двигаться либо только вправо, либо вниз.
Примеры:
Input: mat[][] = {{1, 2, 3}, {4, 5, 6}}, s[] = {0, 0}, d[]={1, 2}
Output:
1 4 5 6
1 2 5 6
1 2 3 6Input: mat[][] = {{1, 2}, {3, 4}}, s[] = {0, 1}, d[] = {1, 1}
Output: 2 4
Подход: используйте рекурсию для перемещения сначала вправо, а затем вниз от каждой ячейки на пути матрицы mat[][] , начиная с источника, и сохраняйте каждое значение в векторе. Если пункт назначения достигнут, выведите вектор как один из возможных путей. Выполните следующие шаги, чтобы решить проблему:
- Если текущая ячейка находится за границей, то вернуться.
- Поместите значение текущей ячейки в векторный путь [].
- Если текущая ячейка является местом назначения, напечатайте текущий путь.
- Вызовите ту же функцию для значений {i+1, j} и {i, j+1}.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(2 n+m )
Вспомогательное пространство: O(1)