Cod sursa(job #2981435)

Utilizator TeoRoGaming_YgVoinea Ionut-Florin TeoRoGaming_Yg Data 17 februarie 2023 22:16:32
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int max_size = 101, max_dir = 8;

char a[max_size][max_size];
int r[max_size][max_size], jl[max_size][max_size], n, m,
    di[] = {-1, -1, 0, 1, 1, 1, 0, -1},
    dj[] = {0, 1, 1, 1, 0, -1, -1, -1};

queue <pair <int,int>> coada;

void lee1 (int is, int js)
{
    r[is][js] = 1;
    coada.push(make_pair(is, js));
    while (!coada.empty())
    {
        int i = coada.front().first, j = coada.front().second;
        for (int k = 0; k < max_dir; k++)
        {
            int iv = i + di[k], jv = j + dj[k];
            if (iv >= 0 && jv >= 0 && iv < n && jv < m && (r[iv][jv] == 0 || r[i][j] + 1 < r[iv][jv]))
            {
                r[iv][jv] = r[i][j] + 1;
                coada.push(make_pair(iv, jv));
            }
        }
        coada.pop();
    }
}

void lee2 (int is, int js)
{
    jl[is][js] = 1;
    coada.push(make_pair(is, js));
    while (!coada.empty())
    {
        int i = coada.front().first, j = coada.front().second;
        for (int k = 0; k < max_dir; k++)
        {
            int iv = i + di[k], jv = j + dj[k];
            if (iv >= 0 && jv >= 0 && iv < n && jv < m && (jl[iv][jv] == 0 || jl[i][j] + 1 < jl[iv][jv]))
            {
                jl[iv][jv] = jl[i][j] + 1;
                coada.push(make_pair(iv, jv));
            }
        }
        coada.pop();
    }
}

int main ()
{
    f >> n >> m;
    f.get();
    int ir, jr, ij, jj;
    for (int i = 0; i < n; i++)
    {
        f.getline(a[i], max_size + 1);
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == ' ')
            {
                r[i][j] = 0;
                jl[i][j] = 0;
            }
            if (a[i][j] == 'X')
            {
                r[i][j] = -1;
                jl[i][j] = -1;
            }
            if (a[i][j] == 'R')
            {
                r[i][j] = 0;
                jl[i][j] = 0;
                ir = i;
                jr = j;
            }
            if (a[i][j] == 'J')
            {
                r[i][j] = 0;
                jl[i][j] = 0;
                ij = i;
                jj = j;
            }
        }
    }
    lee1(ir, jr);
    lee2(ij, jj);
    int irez, jrez, rez = 1e9 + 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (r[i][j] != -1 && r[i][j] != 0 && r[i][j] == jl[i][j])
            {
                if (r[i][j] < rez)
                {
                    rez = r[i][j];
                    irez = i;
                    jrez = j;
                }
            }
        }
    }
    g << rez << " " << irez + 1 << " " << jrez + 1;
    return 0;
}