Cod sursa(job #2785648)

Utilizator PatruMihaiPatru Mihai PatruMihai Data 19 octombrie 2021 09:59:28
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

const int lmax = 107;

struct pereche
{
    int x, y;
} rs, js;

struct matrice
{
    int nr, romeo, julieta;
};

matrice v[lmax][lmax];
int n, m;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};

int inmat(int x, int y)
{
    return x >= 1 && y >= 1 && x <= n && y <= m;
}

void leer(int x, int y)
{
    queue<pereche> q;
    v[x][y].romeo = 1;
    q.push(pereche{x, y});

    while (!q.empty())
    {
        int i = q.front().x;
        int j = q.front().y;
        q.pop();
        for (int d = 0; d < 8; d++)
        {
            int diri = i + dx[d];
            int dirj = j + dy[d];
            if (inmat(diri, dirj) && v[diri][dirj].nr == 0 && v[diri][dirj].romeo == 0)
            {
                v[diri][dirj].romeo = v[i][j].romeo + 1;
                q.push(pereche{diri, dirj});
            }
        }
    }
}

void leej(int x, int y)
{
    queue<pereche> q;
    v[x][y].julieta = 1;
    q.push(pereche{x, y});

    while (!q.empty())
    {
        int i = q.front().x;
        int j = q.front().y;
        q.pop();
        for (int d = 0; d < 8; d++)
        {
            int diri = i + dx[d];
            int dirj = j + dy[d];
            if (inmat(diri, dirj) && v[diri][dirj].nr == 0 && v[diri][dirj].julieta == 0)
            {
                v[diri][dirj].julieta = v[i][j].julieta + 1;
                q.push(pereche{diri, dirj});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    fin.get();
    for (int i = 1; i <= n; i++)
    {
        string s;
        getline(fin, s);
        for (int j = 0; j < m; j++)
        {
            if (s[j] == 'R')
            {
                rs = pereche{i, j + 1};
            }
            else if (s[j] == 'J')
            {
                js = pereche{i, j + 1};
            }
            else if (s[j] == 'X')
            {
                v[i][j + 1].nr = -1;
            }
        }
    }

    /*for(int i = 1; i <= n; i++)
    {
        for(int j =  1; j <= m; j++)
        {
            fout << v[i][j].nr << " ";
        }
        fout << "\n";
    }*/

    
    leer(rs.x, rs.y);
    leej(js.x, js.y);

    pereche intalnire;

    int minim = 999999999;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (v[i][j].romeo > 0 && v[i][j].julieta > 0 && v[i][j].romeo == v[i][j].julieta && minim > v[i][j].romeo)
            {
                minim = v[i][j].romeo;
                intalnire = pereche{i, j};
            }
        }
    }
    fout << minim << " " << intalnire.x << " " << intalnire.y;

    return 0;
}