Как лучше хранить кратчайший путь и его длину в лабиринте?

Question

Я использую алгоритм Ли, чтобы найти кратчайший путь в лабиринте.

Лабиринт состоит из 0 и 1. Ячейка со значением 1 представляет собой пустое пространство, к которому можно go, ячейка со значением 0 - это препятствие, которое нельзя пройти.

Однако, выполняя часть q.pop() внутри while(!q.isEmpty()) l oop, я теряю свои «узлы» (я реализовал структуру pozitie_plan, в которой хранится индекс строки, индекс столбца и расстояние между произвольно выбранной точкой в ​​матрице и самой собой). Эти «узлы» могут быть частью пути, который я хочу вывести в конце. Тем не менее, я думаю, что я не должен изменять эту часть.

Я ограничен в использовании очереди в DLLA (Dynami c Linked List on Array). Я реализовал свой собственный. При необходимости я также добавлю его реализацию.

Способ, которым я нахожу путь, заключается в определении наименьшей длины с использованием алгоритма Ли и оставлении следа на вспомогательной матрице, значение в (i, j ) ячейка, представляющая расстояние от источника до этой ячейки.

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

Я держу эти pozitie_plan узлы в очереди, затем возвращаю очередь в конце и вывод окончательного результата.

Я чувствую, что это может быть сделано лучше. Но как?

Вот мой код. Если потребуется, я могу отредактировать сообщение и изменить опубликованный код на версию, имеющую несколько cout с и более комментариев и / или реализацию для Очереди.

main. cpp

#include <iostream>
#include <vector>
#include "Queue.h"
#include "ShortTest.h"
#include "ExtendedTest.h"

#define Nmax 25

using std::cin;
using std::cout;
using std::vector;
using std::swap;

#include <fstream>
using std::ifstream;
using std::ofstream;


template<typename T>
void citeste_mat(ifstream &input_stream, T mat[][Nmax], int &n, int &m)
{
    input_stream >> n >> m; 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            input_stream >> mat[i][j];
}

void citeste_poz_start(ifstream &input_stream, pozitie_plan &p)
{
    input_stream >> p.i >> p.j;
    p.dist = 0;
    p.i--; p.j--;               // utilizatorul vede in indexare de la 1, dar eu am implementat in indexare de la 0!
}

template<typename V>
void citeste_date(ifstream &input_file, V mat[][Nmax], int &n, int &m, pozitie_plan &p)
{
    citeste_mat<V>(input_file, mat, n, m);
    citeste_poz_start(input_file, p);
}

template<typename U> // ar fi fost problema daca puneam aici tot "T" in loc de "U" ?
void afis_mat(U mat[][Nmax], int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << mat[i][j] << " ";
        cout << '\n';
    }
    cout << '\n';
}

bool valid_pozitie( int i, int j, int n, int m)
{
    return 0 <= i && i < n && 0 <= j && j < m;
}

template<typename T>
bool obstacol(T mat[][Nmax], pozitie_plan p)
{
    return mat[p.i][p.j] == 0;
}

template<typename T>
bool valid_nevizitat(T aux[][Nmax], pozitie_plan p)
{
    return aux[p.i][p.j] == false;
}

template<typename T, typename U>
bool valid(T mat[][Nmax], U aux[][Nmax], pozitie_plan p, int n, int m)
{
    return valid_pozitie(p.i, p.j, n, m) && !obstacol<T>(mat, p) && valid_nevizitat<U>(aux, p);
}

// e un pic "overhead" sa am toate functiile astea de valid, stiu; dar parca imi place sa am totul cat se poate de fragmentat

bool pe_contur(pozitie_plan p, int n, int m)
{
    // return p.i == 0 || p.j == 0 || p.i == n - 1 || p.j == m - 1;
    return p.i * p.j == 0 || p.i == n-1 || p.j == m-1;
}

template<typename T>
bool solution(T mat[][Nmax], pozitie_plan p , int n, int m)
{
    return !obstacol(mat, p) && pe_contur(p, n, m);
}


template<typename T>
pozitie_plan gaseste_cale(T mat[][Nmax], int n, int m, pozitie_plan ps)
{
    // voi pastra integritatea matricii ( mat nu va fi modificata )

    const int dx[] = { -1, 0, 1, 0 };
    const int dy[] = { 0, 1, 0, -1};

    bool visited[Nmax][Nmax] = { false };

    visited[ps.i][ps.j] = true;             // marchez pozitia de start ca vizitata 

    Queue q;
    q.push(ps);                             // bag in coada pozitia de start

    pozitie_plan current_pos;
    int row, column, distance;

    while (!q.isEmpty())
    // cat timp exista in coada pozitii pentru care trebuie verificati vecinii (daca vecinii sunt iesire sau nu)
    {
        current_pos = q.top();
        if (solution<int>(mat, current_pos, n, m))
        {
            return current_pos; // voi returna prima solutie gasita, care garantat va fi cea mai scurta (BFS)
        }

        q.pop();        // stocand head ul in `current_pos` pot spune ca am tratat ce aveam in head, asa cu fac pop

        for (int k = 0; k < 4; k++)
        {
            row = current_pos.i + dx[k];
            column = current_pos.j + dy[k];
            distance = current_pos.dist + 1;

            pozitie_plan vecin{ row, column, distance };

            if (valid<int,bool>(mat, visited, vecin, n, m))

            {
                mat[row][column] = distance;
                visited[row][column] = true;
                q.push(vecin);
            }
        }
    }

    return NULL_POZITIE_PLAN;
}

void reconstruct_path(int mat[][Nmax], int n, int m, pozitie_plan end, pozitie_plan begin, Queue& q)
{
    const int dx[] = { -1, 0, 1, 0 };
    const int dy[] = { 0, 1, 0, -1 };

    q.push(end);

    pozitie_plan current_pos = end;
    int row, column, distance;
    int len = current_pos.dist;
    while(len != 1)
    {
        for (int k = 0; k < 4; k++)
        {
            row = current_pos.i + dx[k];
            column = current_pos.j + dy[k];
            distance = mat[row][column];
            if (valid_pozitie(row, column, n, m)
                && distance == len - 1)
            {
                pozitie_plan new_pos = pozitie_plan{ row, column, distance };
                q.push(new_pos);
                current_pos = new_pos;
                break;
            }
        }
        len--;
    }
    q.push(begin);
}


void reverse_queue(Queue& q, const int len)
{
    pozitie_plan *aux = new pozitie_plan[len];
    for (int i = 0; i < len; i++)
        aux[i] = q.pop();

    for (int i = 0; i < len / 2; i++)
        swap(aux[i], aux[len - 1 - i]);

    for (int i = 0; i <len ; i++)
        q.push(aux[i]);
}


int main()
{

    int mat[Nmax][Nmax] = { 0 };
    int n, m;
    pozitie_plan pozitie_start;

    ifstream input_file;
    input_file.open("input.txt", ios::in);
    citeste_date<int>(input_file, mat, n, m, pozitie_start);        
    input_file.close();

    afis_mat<int>(mat, n, m);

    // pana aici citesc datele de intrare

    pozitie_plan end = gaseste_cale<int>(mat, n, m, pozitie_start); // presupun ca utilizatorul numara liniile & coloanele de la 1
    if (end == NULL_POZITIE_PLAN) 
    {
        cout << "NO SOLUTION FOUND!\n";
    }
    else
    {
        // Queue cale = reconstruct_path(mat, n, m, end);
        Queue cale;
        reconstruct_path(mat, n, m, end, pozitie_start, cale);
        reverse_queue(cale, end.dist + 1);  
        cout << "The shortest path (length = " << end.dist << " not including the starting position) to be followed in the given matrix (above) is:\n";
        cale.toString();
    }
    return 0;
}

Пример

input.txt

18 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
17 3

консольный выход

The shortest path...// everything is ok, the path is ok