Cod sursa(job #2443456)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 28 iulie 2019 00:00:16
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <cstring>

using namespace std;

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

struct gigi
{
    int x;
    int y;
};

int r[105][105];
int j[105][105];
gigi cr[10005];
gigi cj[10005];
gigi d[9];
char v[105];

int main()
{
    d[0].x = -1; d[1].x = 0; d[2].x = 1; d[3].x = 0; d[4].x = -1; d[5].x = 1; d[6].x = 1; d[7].x = -1;
    d[0].y = 0; d[1].y = -1; d[2].y = 0; d[3].y = 1; d[4].y = -1; d[5].y = -1; d[6].y = 1; d[7].y = 1;
    int n, m, x1, x2, y1, y2;
    fin >> n >> m;
    fin.getline(v, m + 1);
    for (int i = 0; i < n; i++)
    {
        fin.getline(v, m + 1);
        for (int k = 1; k <= m; k++)
        {
            if (v[k - 1] == 'X')
            {
                r[i + 1][k] = -1;
                j[i + 1][k] = -1;
            }
            if (v[k - 1] == 'J')
            {
                x1 = i + 1;
                y1 = k;
            }
            if (v[k - 1] == 'R')
            {
                x2 = i + 1;
                y2 = k;
            }
        }
    }
    for (int i = 0; i <= n + 1; i++)
    {
        r[i][0] = -1;
        r[i][m + 1] = -1;
        j[i][0] = -1;
        j[i][m + 1] = -1;
    }
    for (int i = 0; i <= m + 1; i++)
    {
        r[0][i] = -1;
        r[n + 1][i] = -1;
        j[0][i] = -1;
        j[n + 1][i] = -1;
    }
    int prim = 0, ultim = 0, vlin, vcol;
    r[x2][y2] = 1;
    cr[prim].x = x2;
    cr[prim].y = y2;
    while (prim <= ultim)
    {
        for (int i = 0; i <= 7; i++)
        {
            vlin = cr[prim].x + d[i].x;
            vcol = cr[prim].y + d[i].y;
            if (r[vlin][vcol] == 0)
            {
                r[vlin][vcol] = r[cr[prim].x][cr[prim].y] + 1;
                ultim++;
                cr[ultim].x = vlin;
                cr[ultim].y = vcol;
            }
        }
        prim++;
    }
    prim = 0;
    ultim = 0;
    j[x1][y1] = 1;
    cj[prim].x = x1;
    cj[prim].y = y1;
    while (prim <= ultim)
    {
        for (int i = 0; i <= 7; i++)
        {
            vlin = cj[prim].x + d[i].x;
            vcol = cj[prim].y + d[i].y;
            if (j[vlin][vcol] == 0)
            {
                j[vlin][vcol] = j[cj[prim].x][cj[prim].y] + 1;
                ultim++;
                cj[ultim].x = vlin;
                cj[ultim].y = vcol;
            }
        }
        prim++;
    }
    int lmin = INT_MAX, x3 = 0, y3 = 0;
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= m; k++)
            if (r[i][k] == j[i][k] && r[i][k] < lmin && r[i][k] > 0)
            {
                lmin = r[i][k];
                x3 = i;
                y3 = k;
            }
    fout << lmin << ' ' << x3 << ' ' << y3 << '\n';
    return 0;
}