Cod sursa(job #2576058)

Utilizator corvinus2003Corvin Ghita corvinus2003 Data 6 martie 2020 17:05:58
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.11 kb
///Lee din doua puncte
#include <bits/stdc++.h>

using namespace std;

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

string s;
int ar[105][105], aj[105][105], n, m;
int rx, ry, jx, jy;
int dx[] = {0,-1,-1,-1, 0, 1, 1, 1};
int dy[] = {1, 1, 0,-1,-1,-1, 0, 1};

struct pos
{
    int x, y;
};

queue <pos> r;
queue <pos> j;
pos rcurent, jcurent;
pos rinsert, jinsert;

void bordare()
{
    for (int i = 0; i <= n + 1; ++i)
        ar[i][0] = ar[i][m + 1] = aj[i][0] = aj[i][m + 1] = -1;
    for (int j = 0; j <= m + 1; ++j)
        ar[0][j] = ar[n + 1][j] = aj[0][j] = aj[n + 1][j] = -1;
}

void citire()
{
    getline(fin, s);
    for (int i = 1; i <= n; ++i)
    {
        getline(fin, s);
        for (int j = 0; j < m; ++j)
        {
            if (s[j] == 'R')
            {
                rx = i;
                ry = j + 1;
            }
            if (s[j] == 'J')
            {
                jx = i;
                jy = j + 1;
            }
            if (s[j] == 'X')
            {
                ar[i][j + 1] = aj[i][j + 1] = -1;
            }
        }
    }
    ar[rx][ry] = ar[jx][jy] = aj[rx][ry] = aj[jx][jy] = 1;
}

void afisare()
{
    for (int i = 0; i <= n + 1; ++i)
    {
        for (int j = 0; j <= m + 1; ++j)
            fout << ar[i][j] << '\t';
        fout << '\n';
    }
    for (int i = 0; i <= n + 1; ++i)
    {
        for (int j = 0; j <= m + 1; ++j)
            fout << aj[i][j] << '\t';
        fout << '\n';
    }
}

void rlee()
{
    rcurent.x = rx;
    rcurent.y = ry;
    r.push(rcurent);
    while (!r.empty())
    {
        rcurent.x = r.front().x;
        rcurent.y = r.front().y;
        r.pop();
        for (int i = 0; i < 8; ++i)
        {
            rinsert.x = rcurent.x + dx[i];
            rinsert.y = rcurent.y + dy[i];
            if (ar[rinsert.x][rinsert.y] == 0)
            {
                ar[rinsert.x][rinsert.y] = ar[rcurent.x][rcurent.y] + 1;
                r.push(rinsert);
            }
        }
    }
}

void jlee()
{
    jcurent.x = jx;
    jcurent.y = jy;
    j.push(jcurent);
    while (!j.empty())
    {
        jcurent.x = j.front().x;
        jcurent.y = j.front().y;
        j.pop();
        for (int i = 0; i < 8; ++i)
        {
            jinsert.x = jcurent.x + dx[i];
            jinsert.y = jcurent.y + dy[i];
            if (aj[jinsert.x][jinsert.y] == 0)
            {
                aj[jinsert.x][jinsert.y] = aj[jcurent.x][jcurent.y] + 1;
                j.push(jinsert);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    bordare();
    citire();
    rlee();
    jlee();
    //afisare();
    int tmin = 10005, x, y;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (ar[i][j] > 1 && ar[i][j] == aj[i][j])
            {
                if (ar[i][j] < tmin)
                {
                    tmin = ar[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }
    fout << tmin << ' ' << x << ' ' << y;
    return 0;
}