Cod sursa(job #2575279)

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

using namespace std;

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

string s;
int a[101][101], 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;

struct data
{
    int x, y, z;
};

data ans[200];
int nrans;

bool cmp(data a, data b)
{
    if (a.z < b.z)
        return 1;
    if (a.z > b.z)
        return 0;
    if (a.x < b.x)
        return 1;
    if (a.x > b.x)
        return 0;
    if (a.y <= b.y)
        return 1;
    return 0;
}

void bordare()
{
    for (int i = 0; i <= n + 1; ++i)
        a[i][0] = a[i][m + 1] = -1;
    for (int j = 0; j <= m + 1; ++j)
        a[0][j] = a[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')
            {
                a[i][j + 1] = -1;
            }
        }
    }
    a[rx][ry] = a[jx][jy] = 1;
}

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

int main()
{
    fin >> n >> m;
    bordare();
    citire();
    rcurent.x = rx;
    rcurent.y = ry;
    jcurent.x = jx;
    jcurent.y = jy;
    r.push(rcurent);
    j.push(jcurent);
    while (!r.empty() && !j.empty())
    {
        rcurent.x = r.front().x;
        rcurent.y = r.front().y;
        r.pop();
        jcurent.x = j.front().x;
        jcurent.y = j.front().y;
        j.pop();
        for (int i = 0; i < 8; ++i)
        {
            rinsert.x = rcurent.x + dx[i];
            rinsert.y = rcurent.y + dy[i];
            jinsert.x = jcurent.x + dx[i];
            jinsert.y = jcurent.y + dy[i];
            ///S-a intalnit cu Julieta
            if (a[rinsert.x][rinsert.y] == a[rcurent.x][rcurent.y] + 1)
            {
                ans[nrans].x = rinsert.x;
                ans[nrans].y = rinsert.y;
                ans[nrans].z = a[rinsert.x][rinsert.y];
                nrans++;
            }
            else if (a[rinsert.x][rinsert.y] == 0)
            {
                a[rinsert.x][rinsert.y] = a[rcurent.x][rcurent.y] + 1;
                r.push(rinsert);
            }
            ///S-a intalnit cu Romeo
            if (a[jinsert.x][jinsert.y] == a[jcurent.x][jcurent.y] + 1)
            {
                ans[nrans].x = jinsert.x;
                ans[nrans].y = jinsert.y;
                ans[nrans].z = a[jinsert.x][jinsert.y];
                nrans++;
            }
            else if (a[jinsert.x][jinsert.y] == 0)
            {
                a[jinsert.x][jinsert.y] = a[jcurent.x][jcurent.y] + 1;
                j.push(jinsert);
            }
        }
    }
    sort(ans, ans + nrans, cmp);
    fout << ans[0].z << ' ' << ans[0].x << ' ' << ans[0].y;
    return 0;
}