Cod sursa(job #2667563)

Utilizator andrei.calin25Calin Andrei andrei.calin25 Data 3 noiembrie 2020 17:27:29
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <climits>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

struct punct { int linie, coloana;} R, J;
char matrice[101][101];
int n, m, mr[101][101], mj[101][101];
int minim = INT_MAX;
punct coordonate_min;
queue<punct> coada;

void citire() {

    string rand;

    f>>n>>m;
    getline(f, rand);

    for(int i=1; i<=n; i++) {

        getline(f, rand);
        if(rand.length() < m)
            rand = rand + ' ';

        for (int j = 1; j <= m; j++) {
            matrice[i][j] = rand[j - 1];

            if (matrice[i][j] == 'R')
                R.linie=i, R.coloana=j;
            if (matrice[i][j] == 'J')
                J.linie=i, J.coloana=j;
        }
    }
}

void bfs_r() {

    while(!coada.empty()) {
        punct crt = coada.front();
        coada.pop();

        int i, j;
        punct x;
        for(i=-1; i<=1; i++)
            for(j=-1; j<=1; j++)
                if(!(i==0 && j==0)) {
                    x.linie = crt.linie + i;
                    x.coloana = crt.coloana + j;

                    if(matrice[x.linie][x.coloana] == ' ' && mr[x.linie][x.coloana] == 0) {
                        mr[x.linie][x.coloana] = mr[crt.linie][crt.coloana] + 1;
                        coada.push(x);
                    }
                }


    }
}

void bfs_j() {

    while(!coada.empty()) {
        punct crt = coada.front();
        coada.pop();

        int i, j;
        punct x;
        for(i=-1; i<=1; i++)
            for(j=-1; j<=1; j++)
                if(!(i==0 && j==0)) {
                    x.linie = crt.linie + i;
                    x.coloana = crt.coloana + j;

                    if(matrice[x.linie][x.coloana] == ' ' && mj[x.linie][x.coloana] == 0) {
                        mj[x.linie][x.coloana] = mj[crt.linie][crt.coloana] + 1;
                        coada.push(x);
                    }
                }


    }
}

void intalnire() {

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if (mr[i][j] == mj[i][j] && mr[i][j] > 0)
                if (mr[i][j] < minim) {

                    minim = mr[i][j];
                    coordonate_min.linie = i;
                    coordonate_min.coloana = j;
                }
}

int main() {

    citire();

    coada.push(R);
    mr[R.linie][R.coloana]=1;
    bfs_r();

    while (!coada.empty())
        coada.pop();

    coada.push(J);
    mj[J.linie][J.coloana]=1;
    bfs_j();

//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            if (matrice[i][j] == ' ')
//                cout<<mr[i][j]<<" ";
//            else
//                cout<<matrice[i][j]<<" ";
//            cout<<endl;
//    }
//
//    cout<<"________________________"<<endl;
//
//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            if (matrice[i][j] == ' ')
//                cout<<mj[i][j]<<" ";
//            else
//                cout<<matrice[i][j]<<" ";
//        cout<<endl;
//    }

    intalnire();

    g<<minim<<" "<<coordonate_min.linie<<" "<<coordonate_min.coloana;


}