Выведите все возможные пути выхода из матрицы из заданной позиции, используя не более K ходов.

Имея матрицу mat[][] размерности N*M , натуральное число K и исходную ячейку (X, Y) , задача состоит в том, чтобы напечатать все возможные пути выхода из матрицы из исходной ячейки (X, Y ) , двигаясь во всех четырех направлениях на каждом ходу не более чем за K ходов.

Примеры:

Input: N = 2, M = 2, X = 1, Y = 1, K = 2
Output:
(1 1)(1 0)
(1 1)(1 2)(1 3)
(1 1)(1 2)(0 2)
(1 1)(0 1)
(1 1)(2 1)(2 0)
(1 1)(2 1)(3 1)

Input: N = 1, M = 1, X = 1, Y = 1, K = 2
Output:
(1 1)(1 0)
(1 1)(1 2)
(1 1)(0 1)
(1 1)(2 1)

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

• Инициализируйте массив, скажем, arrayOfMoves[] , в котором хранятся все ходы, перемещающиеся из исходной ячейки в исходную часть матрицы.
• Определите рекурсивную функцию, скажем, printAllmoves(N, M, moves, X, Y, arrayOfMoves) и выполните следующие шаги:
  • Базовый вариант:
    • Если значение ходов неотрицательно и текущая ячейка (X, Y) находится вне матрицы, то выведите все ходы, хранящиеся в ArrayOfMoves[] .
    • Если значение moves меньше 0 , то возвращаемся из функции.
  • Вставьте текущую ячейку (X, Y) в массив arrayOfMoves[] .
  • Рекурсивно вызывать функцию во всех четырех направлениях текущей ячейки (X, Y) , уменьшая значение moves на 1
  • Если размер массива arrayOfMoves[] больше 1, удалите последнюю ячейку, вставленную для шагов возврата.
• Вызовите функцию printAllmoves(N, M, moves, X, Y, arrayOfMoves), чтобы распечатать все возможные ходы.

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

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