Cod sursa(job #2793031)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 2 noiembrie 2021 18:43:20
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 9.78 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;

class Graf {
    int n;
    int m;
    vector<int> vecini[100002];
public:
    Graf(int n);
    Graf(int n, int m, pair<int, int> muchii[], bool directed);
    Graf(int n, vector< vector<int> > muchii, bool directed);
    void adaugaMuchie(int x, int y, bool orientata);
    int nrComponenteConexe();
    vector<int> bfs(int srs);
    vector<int> sortareTopologica();
    vector< vector<int> > componenteTareConexe();
    vector< vector<int> > componenteBiconexe();
    vector< vector<int> > muchiiCritice();
private:
    void dfs(int nod, vector<bool> &viz);
    void dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz);
    void dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s, vector<bool> &inStack,
                       vector< vector<int> > &componente, int &cnt, vector<bool> &viz);
    void dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &viz);
};

Graf :: Graf(int n) {
    this->n = n;
    this->m = 0;
}

Graf :: Graf(int n, int m, pair<int, int> muchii[], bool directed) {
    this->n = n;
    this->m = m;
    for (int i = 1; i <= m; i++) {
        vecini[ muchii[i].first ].push_back(muchii[i].second);
        if (!directed) {
            vecini[ muchii[i].second ].push_back(muchii[i].first);
        }
    }
}

Graf :: Graf(int n, vector< vector<int> > muchii, bool directed) {
    this->n = n;
    this->m = muchii.size();
    for (int i = 0; i < muchii.size(); i++) {
        vecini[ muchii[i][0] ].push_back(muchii[i][1]);
        if (!directed) {
            vecini[ muchii[i][1] ].push_back(muchii[i][0]);
        }
    }
}

void Graf :: adaugaMuchie(int x, int y, bool orientata) {
    vecini[x].push_back(y);
    if (!orientata) {
        vecini[y].push_back(x);
    }
}

int Graf :: nrComponenteConexe() {
    vector<bool> viz;
    viz.resize(n + 1);
    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            nr++;
            dfs(i, viz);
        }
    }
    return nr;
}
void Graf :: dfs(int nod, vector<bool> &viz) {
    viz[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        if (!viz[ vecini[nod][i] ]) {
            dfs(vecini[nod][i], viz);
        }
    }
}
vector<int> Graf :: bfs(int srs) {
    vector<int> dist;
    dist.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    queue<int> q;
    q.push(srs);
    dist[srs] = 0;
    while (!q.empty()) {
        int nod = q.front();
        for (int i = 0; i < vecini[nod].size(); i++) {
            int vecin = vecini[nod][i];
            if (dist[vecin] == -1) {
                dist[vecin] = dist[nod] + 1;
                q.push(vecin);
            }
        }
        q.pop();
    }
    return dist;
}

vector<int> Graf :: sortareTopologica() {
    vector<int> noduriSortate;
    vector<bool> viz;
    viz.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsSortare(i, noduriSortate, viz);
        }
    }
    for (int i = 0; i < n / 2; i++) {
        swap(noduriSortate[i], noduriSortate[n - i - 1]);
    }
    return noduriSortate;
}

void Graf :: dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz) {
    viz[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!viz[vecin]) {
            dfsSortare(vecin, noduriSortate, viz);
        }
    }
    noduriSortate.push_back(nod);
}

vector< vector<int> > Graf :: componenteTareConexe() {
    vector<int> level, low;
    vector<bool> inStack, viz;
    level.resize(n + 1);
    low.resize(n + 1);
    inStack.resize(n + 1);
    viz.resize(n + 1);
    int cnt = 0;
    vector< vector<int> > componente;
    stack<int> s;
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfsTareConexe(i, level, low, s, inStack, componente, cnt, viz);
        }
    }
    return componente;
}

void Graf :: dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s,
                vector<bool> &inStack, vector< vector<int> > &componente, int &cnt, vector<bool> &viz) {

    viz[nod] = true;
    cnt++;
    level[nod] = low[nod] = cnt;
    s.push(nod);
    inStack[nod] = true;
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (!viz[vecin]) {
            dfsTareConexe(vecin, level, low, s, inStack, componente, cnt, viz);
        }
        if (inStack[vecin]) {
            low[nod] = min(low[nod], low[vecin]);
        }
    }
    if (low[nod] == level[nod]) {
        vector<int> noduriComponenta;
        int nodComponenta;
        do {
            nodComponenta = s.top();
            inStack[nodComponenta] = 0;
            s.pop();
            noduriComponenta.push_back(nodComponenta);
        } while (nodComponenta != nod);
        componente.push_back(noduriComponenta);
    }
}

vector< vector<int> > Graf :: componenteBiconexe() {
    vector<int> level, low;
    vector<bool>  viz;
    level.resize(n + 1);
    low.resize(n + 1);
    viz.resize(n + 1);
    vector< vector<int> > componente;
    stack<int> s;
    dfsBiconexe(1, 0, level, low, s, componente, viz);
    return componente;
}

vector< vector<int> > Graf :: muchiiCritice() {
    vector<int> level, low;
    vector<bool>  viz;
    level.resize(n + 1);
    low.resize(n + 1);
    viz.resize(n + 1);
    vector< vector<int> > componente, critice;
    stack<int> s;
    dfsBiconexe(1, 0, level, low, s, componente, viz);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < vecini[i].size(); j++) {
            if (low[ vecini[i][j] ] > level[i]) {
                vector<int> muchie;
                muchie.push_back(i);
                muchie.push_back(vecini[i][j]);
                critice.push_back(muchie);
            }
        }
    }
    return critice;
}

void Graf:: dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
                     vector< vector<int> > &componente, vector<bool> &viz) {

    viz[nod] = 1;
    level[nod] = low[nod] = level[tata] + 1;
    s.push(nod);
    for (int i = 0; i < vecini[nod].size(); i++) {
        int vecin = vecini[nod][i];
        if (vecin == tata) {
            continue;
        }
        if (viz[vecin] == 1) {
            low[nod] = min(low[nod], level[vecin]);
            continue;
        }
        dfsBiconexe(vecin, nod, level, low, s, componente, viz);
        low[nod] = min(low[nod], low[vecin]);
        if (low[vecin] >= level[nod]) {
            vector<int> componenta;
            componenta.push_back(nod);
            int nodComponenta;
            do{
                nodComponenta = s.top();
                componenta.push_back(nodComponenta);
                s.pop();
            } while (nodComponenta != vecin);
            componente.push_back(componenta);
        }
    }
}

bool havelHakimi(int n, vector<int> g) {
    int i, ii, k;
    vector<int> fr, fr2;
    fr.resize(n);
    fr2.resize(n);
    for (i = 1; i <= n; i++) {
        if (g[i] < 0 || g[i] >= n) {
            return false;
        }
        fr[ g[i] ]++;
    }
    for (ii = 1; ii <= n; ii++) {
        for (i = n - 1; i >= 1; i--) {
            if (fr[i] > 0) {
                k = i;
                break;
            }
        }
        if (i == 0) {
            return true;
        }
        fr[k]--;
        for (; i >= 1; i--) {
            if (fr[i] < k) {
                k -= fr[i];
                fr2[i - 1] = fr[i];
            }
            else {
                fr2[i - 1] = k;
                fr2[i] += fr[i] - k;
                k = 0;
                break;
            }
        }
        for (i = i - 1; i >= 0; i--) {
            fr2[i] += fr[i];
        }
        if (k > 0) {
            return false;
        }
        for (i = 0; i < n; i++) {
            fr[i] = fr2[i];
            fr2[i] = 0;
        }
    }
}

int n, m, i, j, x, y, isol, jsol, minim, dir, iv, jv;
char a[105][105], s[105];
vector<int> distx, disty;
int di[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dj[8] = {0, 0, -1, 1, -1, 1, -1, 1};
ifstream fin ("rj.in");
ofstream fout("rj.out");
int main() {
     fin>> n >> m;
    for(i = 1; i <= n; i++){
        fin.get();
        fin.get(s, 105);
        j = strlen(s);
        while(j < m){
            s[j] = ' ';
            j++;
        }
        for (j = 1; j <= m; j++) {
            a[i][j] = s[j - 1];
            if (a[i][j] == 'R') {
                x = (i - 1) * m + j;
            }
            if (a[i][j] == 'J') {
                y = (i - 1) * m + j;
            }
        }
    }
    Graf *g = new Graf(n * m);
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i][j] == 'X') {
                continue;
            }
            for (dir = 0; dir < 8; dir++) {
                iv = i + di[dir];
                jv = j + dj[dir];
                if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && a[iv][jv] != 'X'){
                    g->adaugaMuchie((i - 1) * m + j, (iv - 1) * m + jv, true);
                }
            }
        }
    }
    distx = g->bfs(x);
    disty = g->bfs(y);
    minim = 10000000;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            int ind = m * (i - 1) + j;
            if (distx[ind] != -1 && distx[ind] == disty[ind] && minim > distx[ind]) {
                minim = distx[ind];
                isol = i;
                jsol = j;
            }
        }
    }
    fout<< minim + 1 <<" "<< isol <<" "<< jsol;
}