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

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

Имея матрицу mat[][] и координаты исходного и конечного узла, задача состоит в том, чтобы найти длину самого длинного пути от источника к месту назначения.

Пример:

Input: mat[][] = {{5, 6, 7, 8}, {4, 1, 0, 9}, {3, 2, 11, 10}}, src = {1, 1}, dest = {2, 2}
Output: 11
Explanation: The longest path between the coordinates (1, 1) and (2, 2) has 11 nodes and the path is given as 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11.

Input: mat = {{5, 4, 1, 0}, {6, 3, 2, 0}, {7, 8, 9, 0}}, src = {0, 1}, dest = {2, 2}
Output: 12

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

  • Применить поиск в глубину от исходного узла к целевому узлу
    • Пройдите в четырех упомянутых направлениях и в каждом узле увеличивайте количество пройденных узлов.
    • Отметьте узлы текущего пути как посещенные в массиве посещенных [][] и рекурсивно вызовите непосещенные узлы во всех четырех направлениях.
    • После достижения узла назначения обновите максимальное количество узлов, которое необходимо пройти, чтобы добраться до места назначения.
  • Поддерживайте максимальное количество узлов на всех путях, что является требуемым ответом.

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


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

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