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

Опубликовано: 20 Сентября, 2022

Учитывая двумерный массив 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 6

Input: 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ