Lab3 - Pb3

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct MATRICE
{
    int valoare = 0, ordin = 0;
};

struct GRAF
{
    vector<vector<int>> ListaAdiac;

    void citire(string fisier, int& ordStart, int& ordDest)
    {
        ifstream fin(fisier);
        if (fin.peek() == EOF) {
            cout << "Fisierul este vid. \n";
        }

        int dim;
        fin >> dim;

        vector<vector<MATRICE>> mat;
        mat.resize(dim);

        int ordin = 0;
        for (int index = 0; index < dim; ++index)
        {
            mat[index].resize(dim);
            for (int index2 = 0; index2 < dim; ++index2)
            {
                int val;
                fin >> val;
                mat[index][index2].valoare = val;
                mat[index][index2].ordin = ordin++;
            }
        }

        formareListe(mat);

        int startLinie, startColoana, destLinie, destColoana;
        fin >> startLinie >> startColoana;
        fin >> destLinie >> destColoana;

        ordStart = mat[startLinie][startColoana].ordin;
        ordDest = mat[destLinie][destColoana].ordin;

        clear(mat);
    }

    bool inMatrice(int x, int y, int dim)
    {
        return (x >= 0 && x < dim&& y >= 0 && y < dim);
    }

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

    void formareListe(vector<vector<MATRICE>> mat)
    {
        ListaAdiac.resize(mat.size() * mat.size());

        for (int index = 0; index < mat.size(); ++index)
            for (int index2 = 0; index2 < mat.size(); ++index2)
            {
                for (int i = 0; i < 4; ++i)
                {
                    int x = index + dx[i] * mat[index][index2].valoare;
                    int y = index2 + dy[i] * mat[index][index2].valoare;

                    if (inMatrice(x, y, mat.size()))
                        ListaAdiac[mat[index][index2].ordin].push_back(mat[x][y].ordin);
                }
            }

        for (int index = 0; index < ListaAdiac.size(); ++index)
            sort(ListaAdiac[index].begin(), ListaAdiac[index].end());
    }

    void afisareListe()
    {

        for (int index = 0; index < ListaAdiac.size(); ++index)
        {
            cout << "L[" << index << "]: ";
            for (int index2 = 0; index2 < ListaAdiac[index].size(); ++index2)
                cout << ListaAdiac[index][index2] << ' ';
            cout << endl;
        }
        cout << endl;
    }

    int BFS(int start, int dest)
    {
        queue<int> coada;
        vector<bool> viz;
        vector<int> dist;

        viz.resize(ListaAdiac.size());
        dist.resize(ListaAdiac.size());

        for (int index = 0; index < ListaAdiac.size(); ++index)
            viz[index] = 0, dist[index] = INT_MAX;

        dist[start] = 0;

        viz[start] = 1;
        coada.push(start);

        while (!coada.empty())
        {
            int cap = coada.front();
            coada.pop();
            for (int index = 0; index < ListaAdiac[cap].size(); index++)
            {
                int succ = ListaAdiac[cap][index];
                if (viz[succ] == 0)
                {
                    viz[succ] = 1;
                    coada.push(succ);

                    dist[succ] = dist[cap] + 1;
                    if (succ == dest)
                        return dist[dest];
                }
            }
        }
        return -1;
    }

    template<typename T>
    void clear(vector<T>& mat)
    {
        for (int index = 0; index < mat.size(); ++index)
        {
            mat[index].clear();
            mat[index].shrink_to_fit();
        }
        mat.clear();
        mat.shrink_to_fit();
    }
};

int main()
{
    GRAF graf;
    int start, dest;
    graf.citire("matrice.in", start, dest);
    graf.afisareListe();

    int dist = graf.BFS(start, dest);
    if (dist != -1)
        cout << "Numarul minim de mutari necesare pentru a ajunge la destinatie: " << dist << endl;
    else
        cout << "Nu s-a putut ajunge la destinatie. \n";

    graf.clear(graf.ListaAdiac);

    return 0;
}