Cod sursa(job #2140119)

Utilizator RoCata1998Anastasiu Catalin RoCata1998 Data 23 februarie 2018 00:42:17
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

void AfiseazaLista(vector<list<int> > L, int n)
{
    int i;
    cout << "\n";
    for (i = 0; i < n; i++)
    {
        cout << i << ": ";
        for (list<int>::iterator k = L[i].begin(); k != L[i].end(); k++)
            cout << *k << " ";
        cout << "\n";
    }
}

/*  0 - 1 - 2 - 3
    |   |   |   |
    4 - 5 - 6 - 7   <-- un graf asociat unei matrice
    |   |   |   |
    8 - 9 - 10- 11
*/
vector<list<pair<int,char> > > CreeazaListaAdiacenta(char** a, int n, int m)
{
    vector<list<pair<int,char> > > L(n * m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            // ma aflu pe nodul i * m + j
            int nord = (i - 1) * m + j;
            int sud = (i + 1) * m + j;
            int est = i * m + j + 1;
            int vest = i * m + j - 1;
            int NV = (i - 1) * m + j - 1;
            int NE = (i - 1) * m + j + 1;
            int SV = (i + 1) * m + j - 1;
            int SE = (i + 1) * m + j + 1;
            
            if (NV >= 0 && NV % m != m - 1)
                L[i * m + j].push_back( make_pair(NV, a[i - 1][j - 1]) );
            if (nord >= 0)
                L[i * m + j].push_back( make_pair(nord, a[i - 1][j]) );
            if (NE >= 0 && NE % m != 0)
                L[i * m + j].push_back( make_pair(NE, a[i - 1][j + 1]) );
            if (vest >= 0 && vest % m != m - 1)
                L[i * m + j].push_back( make_pair(vest, a[i][j - 1]) );
            if (est <= n * m && est % m != 0)
                L[i * m + j].push_back( make_pair(est, a[i][j + 1]) );
            if (SV < n * m && SV % m != m - 1)
                L[i * m + j].push_back( make_pair(SV, a[i + 1][j - 1]) );
            if (sud < n * m)
                L[i * m + j].push_back( make_pair(sud, a[i + 1][j]) );
            if (SE < n * m && SE % m != 0)
                L[i * m + j].push_back( make_pair(SE, a[i + 1][j + 1]) );
        }
    }
    return L;
}

bool EsteCaracterAcceptabil(char x)
{
    return x == ' ' || x == 'R' || x == 'J';
}

vector<list<int> > CreeazaListaAdiacentaRedusa(char** a, int n, int m, int &rom, int &jul)
{
    vector<list<int> > L(n * m);
    
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (a[i][j] == ' ' || a[i][j] == 'R' || a[i][j] == 'J')
        {
            // ma aflu pe nodul cu nr i * m + j
            if (a[i][j] == 'R')
                rom = i * m + j;
            if (a[i][j] == 'J')
                jul = i * m + j;
            
            int nord = (i - 1) * m + j;
            int sud = (i + 1) * m + j;
            int est = i * m + j + 1;
            int vest = i * m + j - 1;
            int NV = (i - 1) * m + j - 1;
            int NE = (i - 1) * m + j + 1;
            int SV = (i + 1) * m + j - 1;
            int SE = (i + 1) * m + j + 1;
            
            if (NV >= 0 && NV % m != m - 1 && EsteCaracterAcceptabil(a[i - 1][j - 1]) )
                L[i * m + j].push_back(NV);
            if (nord >= 0 && EsteCaracterAcceptabil(a[i - 1][j]) )
                L[i * m + j].push_back(nord);
            if (NE >= 0 && NE % m != 0 && EsteCaracterAcceptabil(a[i - 1][j + 1]) )
                L[i * m + j].push_back(NE);
            if (vest >= 0 && vest % m != m - 1 && EsteCaracterAcceptabil(a[i][j - 1]) )
                L[i * m + j].push_back(vest);
            if (est <= n * m && est % m != 0 && EsteCaracterAcceptabil(a[i][j + 1]) )
                L[i * m + j].push_back(est);
            if (SV < n * m && SV % m != m - 1 && EsteCaracterAcceptabil(a[i + 1][j - 1]) )
                L[i * m + j].push_back(SV);
            if (sud < n * m && EsteCaracterAcceptabil(a[i + 1][j]) )
                L[i * m + j].push_back(sud);
            if (SE < n * m && SE % m != 0 && EsteCaracterAcceptabil(a[i + 1][j + 1]) )
                L[i * m + j].push_back(SE);
            
        }
    return L;
}

void ParcurgeGraf(vector<list<int> > L, int n, int m, int romeo, int julieta, int &timp, int &intalnire)
{
    vector<pair<bool, char> > viz(n * m, make_pair(false, '-'));
    queue<int> C1, C2;
    int i, exploreazaR = 1, exploreazaJ = 1, aux;
    
    timp = 1;
    C1.push(romeo);
    viz[romeo] = make_pair(true, 'R');
    C2.push(julieta);
    viz[julieta] = make_pair(true, 'J');
    intalnire = -1;
    while (!C1.empty() && !C2.empty() && intalnire == -1)
    {
        timp++;
        aux = exploreazaR;
        exploreazaR = 0;
        for (int k = 0; k < aux; k++)
        {
            i = C1.front();
            C1.pop();
            for (list<int>::iterator j = L[i].begin(); j != L[i].end(); j++)
                if (!viz[*j].first)
                {
                    viz[*j].first = true;
                    viz[*j].second = 'R';
                    C1.push(*j);
                    exploreazaR++;
                }
        }
        
        aux = exploreazaJ;
        exploreazaJ = 0;
        for (int k = 0; k < aux; k++)
        {
            i = C2.front();
            C2.pop();
            for (list<int>::iterator j = L[i].begin(); j != L[i].end(); j++)
                if (!viz[*j].first)
                {
                    viz[*j].first = true;
                    viz[*j].second = 'J';
                    C2.push(*j);
                    exploreazaJ++;
                }
                else if (viz[*j].second == 'R')
                {
                    intalnire = *j;
                    break;
                }
        }
        
    }
}

int main()
{
    ifstream f("rj.in");
    ofstream g("rj.out");
    vector<list<int> > L;
    char** a, c;
    int n, m, i, j, romeo, julieta, timp, locIntalnire;

    f >> n >> m;
    a = new char*[n];
    for (i = 0; i < n; i++)
        a[i] = new char[m];
    for (i = 0; i < n; i++)
    {
        f.get(c);
         for (j = 0; j < m; j++)
            f.get(a[i][j]); 

    }


    L = CreeazaListaAdiacentaRedusa(a, n, m, romeo, julieta);
    //cout << romeo << "&" << julieta;
    //AfiseazaLista(L, n * m);
    
    ParcurgeGraf(L, n, m, romeo, julieta, timp, locIntalnire);
    
    //cout << "Timp: " << timp << "\nLoc intalnire: " << locIntalnire / m + 1 << ", " << locIntalnire % m + 1 << "\n";
    g << timp << " " << locIntalnire / m + 1 << " " << locIntalnire % m + 1;
    return 0;
}