Самый длинный возможный маршрут в матрице с препятствиями

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

Учитывая матрицу M x N, с несколькими произвольно размещенными препятствиями, вычислите длину максимально возможного маршрута от источника до пункта назначения в матрице. Нам разрешено перемещаться только в соседние клетки, которые не являются препятствиями. Маршрут не может содержать никаких диагональных перемещений, и место, которое однажды было посещено на определенном пути, не может быть посещено снова.

Например, самый длинный путь без препятствий от источника к месту назначения выделен для матрицы ниже. Длина пути 24.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Идея состоит в том, чтобы использовать Backtracking. Мы начинаем с исходной ячейки матрицы, продвигаемся вперед во всех четырех разрешенных направлениях и рекурсивно проверяем, приводят ли они к решению или нет. Если пункт назначения найден, мы обновляем значение самого длинного пути, иначе, если ни одно из вышеперечисленных решений не работает, мы возвращаем false из нашей функции.

Below is C++ implementation of above idea –

// C++ program to find Longest Possible Route in a
// matrix with hurdles
#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 10
  
// A Pair to store status of a cell. found is set to
// true of destination is reachable and value stores
// distance of longest path
struct Pair
{
    // true if destination is found
    bool found;
  
    // stores cost of longest path from current cell to
    // destination cell
    int value;
};
  
// Function to find Longest Possible Route in the
// matrix with hurdles. If the destination is not reachable
// the function returns false with cost INT_MAX.
// (i, j) is source cell and (x, y) is destination cell.
Pair findLongestPathUtil(int mat[R][C], int i, int j,
    int x, int y, bool visited[R][C])
{
  
    // if (i, j) itself is destination, return true
    if (i == x && j == y)
    {
        Pair p = { true, 0 };
        return p;
    }
  
    // if not a valid cell, return false
    if (i < 0 || i >= R || j < 0 || j >= C ||
            mat[i][j] == 0 || visited[i][j])
    {
        Pair p = { false, INT_MAX };
        return p;
    }
  
    // include (i, j) in current path i.e.
    // set visited(i, j) to true
    visited[i][j] = true;
  
    // res stores longest path from current cell (i, j) to
    // destination cell (x, y)
    int res = INT_MIN;
  
    // go left from current cell
    Pair sol = findLongestPathUtil(mat, i, j - 1, x, y, visited);
  
    // if destination can be reached on going left from current
    // cell, update res
    if (sol.found)
        res = max(res, sol.value);
  
    // go right from current cell
    sol = findLongestPathUtil(mat, i, j + 1, x, y, visited);
  
    // if destination can be reached on going right from current
    // cell, update res
    if (sol.found)
        res = max(res, sol.value);
  
    // go up from current cell
    sol = findLongestPathUtil(mat, i - 1, j, x, y, visited);
  
    // if destination can be reached on going up from current
    // cell, update res
    if (sol.found)
        res = max(res, sol.value);
  
    // go down from current cell
    sol = findLongestPathUtil(mat, i + 1, j, x, y, visited);
  
    // if destination can be reached on going down from current
    // cell, update res
    if (sol.found)
        res = max(res, sol.value);
  
    // Backtrack
    visited[i][j] = false;
  
    // if destination can be reached from current cell,
    // return true
    if (res != INT_MIN)
    {
        Pair p = { true, 1 + res };
        return p;
    }
  
    // if destination can"t be reached from current cell,
    // return false
    else
    {
        Pair p = { false, INT_MAX };
        return p;
    }
}
  
// A wrapper function over findLongestPathUtil()
void findLongestPath(int mat[R][C], int i, int j, int x,
                                                  int y)
{
    // create a boolean matrix to store info about
    // cells already visited in current route
    bool visited[R][C];
  
    // initailize visited to false
    memset(visited, false, sizeof visited);
  
    // find longest route from (i, j) to (x, y) and
    // print its maximum cost
    Pair p = findLongestPathUtil(mat, i, j, x, y, visited);
    if (p.found)
        cout << "Length of longest possible route is "
             << p.value;
  
    // If the destination is not reachable
    else
        cout << "Destination not reachable from given source";
}
  
// Driver code
int main()
{
    // input matrix with hurdles shown with number 0
    int mat[R][C] =
    {
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
    };
  
    // find longest path with source (0, 0) and
    // destination (1, 7)
    findLongestPath(mat, 0, 0, 1, 7);
  
    return 0;
}

Выход:

Длина максимально длинного маршрута 24

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

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