Cod sursa(job #2668393)

Utilizator yoanaIoana Grigore yoana Data 4 noiembrie 2020 20:52:54
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int n,m;
int R[105][105];///matrice romeo
int J[105][105];///matrice julieta
char s[105];///sir pentru fiecare linie din fisier
int xR,yR, xJ,yJ;///coordonate
int absc[8] = {0,-1,-1,-1,0,1,1,1};///directiile in care poate merge
int ord[8] = {-1,-1,0,1,1,1,0,-1};
bool ok(int i, int j)
{
    if( i <= 0 || i > n || j <= 0 || j >m)
        return false;

    return true;
}
void lee(int a[][105], int lin, int col)
{
    pair<int,int> elem;
    pair<int,int> v;
    queue<pair<int,int>> coada;

    coada.push(make_pair(lin, col));

    while(!coada.empty())
    {
        elem = coada.front();
        coada.pop();
        for (int i=0; i<8; i++)
        {
            v.first = elem.first + absc[i];
            v.second = elem.second + ord[i];
            if(ok(v.first,v.second))
            if (a[v.first][v.second] == 0)/// unde am spatiu gol construiesc drum nou, daca a fost deja parcurs nu mai poate sa treaca prin el
            {
                coada.push(v);
                a[v.first][v.second] = a[elem.first][elem.second] + 1;
            }
        }
    }
}

int main()
{
    int tmin = 100010,ci, cj;

    f>>n>>m;


    for (int i=1; i<=n; i++)
    {
        f.getline(s,105);///citesc fiecare linie din datele de intrare
        for (int j=0; j<m; j++)
        {
            if (s[j] == 'X')
            {
                {
                    R[i][j+1] =-1;
                    J[i][j+1] = -1;
                }///pun -1 pe unde nu se poate trece
            }

            if (s[j] == 'R')  ///pun 1 in matricea lui romeo unde am r
            {
                R[i][j+1] = 1;
                xR = i;
                yR = j+1;
            }

            if (s[j] == 'J')  ///pun 1 in matricea julietei unde am j
            {
                J[i][j+1] = 1;
                xJ = i;
                yJ = j+1;
            }


        }
    }
    lee(J,xJ,yJ);
    lee(R,xR,yR);


    for(int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (R[i][j] == J[i][j] && R[i][j] > 0 && R[i][j] < tmin)
            {
                tmin = R[i][j];
                ci = i;
                cj = j;
            }
        }
    }

    g<<tmin<<" "<<ci<<" "<<cj;
}