Распечатайте все пути от исходной точки ко всем 4 углам матрицы.

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

Дан двумерный массив arr[][] размера M*N , содержащий 1 и 0 , где 1 означает, что ячейку можно посетить, а 0 — что ячейка заблокирована. Имеется исходная точка (x, y) и задача состоит в том, чтобы напечатать все пути от заданного источника до любого из четырех углов массива (0, 0), (0, N – 1), (M – 1 , 0) и (М – 1, N – 1) .

Примеры:

Input: arr[][] = {{1, 0, 0, 1, 0, 0, 1, 1}, {1, 1, 1, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1}, {0, 1, 1, 1, 1, 0, 0, 1}, {0, 1, 0, 0, 1, 1, 1, 1}, {1, 1, 0, 0, 0, 0, 0, 1} }. source = {4, 2}
Output :  {“DRRUUURRUUR”, “DRRUUULLULLU”, “DRRDRRRD”, “DLDDL”}
Explanation :  All the possible paths from the source to the 4 corners are

Input: arr[][] = {{0, 1, 0}, {0, 0, 0}, {0, 0, 0}}, source = {0, 1}
Output: No possible path

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

  • Инициализируйте вектор строк ans[] для хранения ответа.
  • Рекурсивно вызовите функцию для проверки в каждом из 4 направлений, нажимая текущее направление и посещая ячейку.
  • Если либо указатель пересекает границу, либо ячейка для посещения не является допустимой ячейкой, т. е. ее значение равно 0 , тогда выполняется возврат.
  • В противном случае сохраните текущую ячейку и, достигнув любого из концов, сделайте ее одним из результатов.
  • После выполнения вышеуказанных шагов напечатайте массив ans[] .

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(3 (M*N) )
Вспомогательное пространство: O(3 (M*N) )

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