Найти длину самого длинного пути в матрице с последовательным символом вместе с его путем

Question

Учитывая M * N матрицу символов, найдите длину самого длинного пути в матрице, начиная с заданного источника.

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

Я правильно определил длину последовательности, но в пути есть проблема. путь неверен.
Вот мой код

#include<iostream>
#include<vector>
using namespace std;

//Below array details all 8 posible directions
int row[] = { -1,-1,-1, 0, 0, 1, 1, 1 };
int col[] = { 1, 0, -1, 1,-1, -1,0, 1 };


int length(char arr[][5], int x, int y, char previous, vector<pair<int,int> > &path, int k)
{
    // x and y must be bounded between 0 to 4
    if( x < 0  || x > 4 || y > 4 || y < 0)
       return 0;

    int l = 0;
    int max_length = 0;

    for( int i = 0; i < 8; i++)
    {
        // storing next character in search
        char ch = arr[x+row[i]][y+col[i]];

        //checking whether ch is the next character in the sequence or not
        if(ch == previous + 1)
        {  
            //if k != path.size() then we have taken back in
            // the sequence so no need to push back character in the path
            if(k == path.size())
              {
                // Pushing co-ordinates of next valid character
                path.push_back(make_pair(x+row[i], y+col[i]));
              }
            else
                path.pop_back();

            l = 1 + length(arr, x+row[i], y+ col[i], ch , path, ++k);
            max_length = max( l, max_length);
        }

    }

    return max_length;
}

int main()
{
    char arr[5][5] = { 
                      { 'd','e','h','x','b'},
                      { 'a','o','g','p','e'},
                      { 'd','d','c','f','d'},
                      { 'e','b','e','a','s'},
                      { 'c','d','y','e','n'}
                    };
    vector<pair<int,int> > path;

    //Pusing source address
    path.push_back(make_pair(2,2));

    int k = 1;

    int Len = length(arr, 2, 2 , arr[2][2], path, k);

    cout << "Length of the Longest sequence is : " << Len + 1 <<endl; 

    //printing the path
    cout << "Path is : "<<endl;
    for( pair<int,int> i : path)
    {
        cout <<"( " << i.first <<","<<i.second <<" )" ;
    }

    return 0;
}

Фактический результат:

Длина самой длинной последовательности: 6
Путь
( 2,2) (2,1) (3,0) (3,2) (2,3) (1,2) (0,2)

Ожидаемая производительность

Длина самой длинной последовательности: 6
Путь
(2,2) (2,1) (3,2) (2,3) (1,2) (0,2)

В моем выводе есть дополнительная (3,0). Когда я возвращаюсь из (3,0), я не могу выдвинуть его.
Любая помощь будет оценена.

Answer 1

Алгоритм построения пути не может работать так. У вас есть предвидение не уничтожать путь при возврате, но когда - после возврата - поиск снова углубляется в другом направлении, путь станет комбинацией двух путей: предыдущая ветвь не удаляется из него.

Итак, в вашем практическом случае первая попытка состоит в go из (2,1) в (3,0). Там он находит, что больше не может go глубже, но пока это лучший путь. Затем он возвращается к (2,1). Путь не сокращен (потому что он все еще лучший). Затем поиск снова углубляется до (3,2). Этот адрес затем добавляется к пути, что делает его несовместимым.

Он не может работать так. Вам нужно создать новый путь, когда вы найдете лучший, и убедиться, что он никогда не будет изменен снова. Только когда вы найдете лучший путь, вы просто полностью его замените.

Я бы также предложил ограничить параметры вашей функции (++k также является проблемой - но мы можем обойтись без). Вместо того, чтобы изменять аргумент пути, пусть функция возвращает самый длинный путь. Длина всегда может быть получена из него.

Так вот как ваша функция может быть изменена:

#include<iostream>
#include<vector>
using namespace std;

//Below array details all 8 posible directions
int row[] = { -1,-1,-1, 0, 0, 1, 1, 1 };
int col[] = { 1, 0, -1, 1,-1, -1,0, 1 };

vector<pair<int,int> > longestPath(char arr[][5], int x, int y)
{
    char previous = arr[x][y];
    vector<pair<int,int> > path; // a new(!) path
    // x and y must be bounded between 0 to 4
    if( x < 0  || x > 4 || y > 4 || y < 0)
       return path;

    for (int i = 0; i < 8; i++)
    {
        // storing next character in search
        char ch = arr[x+row[i]][y+col[i]];

        //checking whether ch is the next character in the sequence or not
        if(ch == previous + 1)
        {  
            vector<pair<int,int> > foundPath = longestPath(arr, x+row[i], y+ col[i]);
            if (foundPath.size() > path.size())
                path = foundPath;
        }

    }
    path.insert(path.begin(), make_pair(x,y));
    return path;
}

int main()
{
    char arr[5][5] = { 
                      { 'd','e','h','x','b'},
                      { 'a','o','g','p','e'},
                      { 'd','d','c','f','d'},
                      { 'e','b','e','a','s'},
                      { 'c','d','y','e','n'}
                    };
    vector<pair<int,int> > path = longestPath(arr, 2, 2);

    //printing the path
    cout << "Path is : "<<endl;
    for( pair<int,int> i : path)
    {
        cout <<"( " << i.first <<","<<i.second <<" )" ;
    }

    return 0;
}

Answer 2

Вместо того, чтобы начинать с реализации и показывать ее нам - вы должны начать с абстрактного алгоритма (и структур данных) и убедиться, что в ваших силах, что , что - это звук. Кроме того, я предлагаю не столько концентрироваться на последовательности отдельных инструкций и l oop переменных, сколько на общей картине.

Итак, вот относительно наивный алгоритм:

• Запустите фазу для каждого узла в (потенциальном) пути: так, в вашем случае, максимум 26 фаз.
• На каждой фазе вы держите набор мест матрицы, где пути могут достигать; и вы получаете набор мест, где эти пути могут достичь с помощью другого шага. Другими словами, вы продвигаете «фронт» из многих путей, по одному шагу за раз.
• Фазовое действие может быть выполнено либо путем попытки двигаться вперед от каждой предыдущей передней позиции (например, проверка, какая «f» впереди есть соседний «g»); или попыткой переместиться назад от каждого элемента матрицы с соответствующим значением для фазы (например, поиск, которые g в матрице смежны с f, которые находятся в предыдущем фронте.)

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

abcde  ...
bcde  ...
cde  ...
de ...
e ...
.
.
.

Любая комбинация движений влево и вниз является допустимым путем; так что есть 2 ^ k путей длины k, начиная с a. Вы хотите вызвать свой longestPath() 2 ^ 26 раз? Нет, если вам не нужно ...: - (