Cod sursa(job #2781660)

Utilizator Stefan_GhinescuGhinescu Stefan-George Stefan_Ghinescu Data 10 octombrie 2021 09:32:42
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <queue>

using namespace std;

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

int dx[] = {-1, -1, 0, 1, 1,  1,  0, -1};
int dy[] = { 0,  1, 1, 1, 0, -1, -1, -1};

int n, m;

int R[105][105], J[105][105];

struct Vec2
{
    int x, y;
};

bool inb(int a, int b)
{
    return 0 <= a && a < n && 0 <= b && b < m;
}

void lee(Vec2 start, int mat[105][105])
{
    queue <Vec2> q;
    q.push(start);
    mat[start.x][start.y] = 1;
    int x, y, xx, yy;
    while (!q.empty())
    {
        x = q.front().x;
        y = q.front().y;
        for (int k = 0; k < 8; ++k)
        {
            xx = x + dx[k];
            yy = y + dy[k];
            if (inb(xx, yy))
            {
                if (mat[xx][yy] == 0)
                {
                    mat[xx][yy] = mat[x][y] + 1;
                    q.push({xx, yy});
                }
            }
        }
        q.pop();
    }
}

int main()
{
    int i, j, mini = 1<<29, x, y;
    char ch[101];
    Vec2 Romeo, Julieta;
    fin >> n >> m;
    fin.get();
    for (i = 0; i < n; ++i)
    {
        fin.getline(ch, m + 1);
        for (j = 0; j < m; ++j)
        {
            if (ch[j] == 'X')
            {
                R[i][j] = -1;
                J[i][j] = -1;
            }
            else if (ch[j] == ' ')
            {
                R[i][j] = 0;
                J[i][j] = 0;
            }
            else if (ch[j] == 'R')
            {
                Romeo = {i, j};
            }
            else if (ch[j] == 'J')
            {
                Julieta = {i, j};
            }
        }
    }
    lee(Romeo, R);
    lee(Julieta, J);
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j < m; ++j)
        {
            if (R[i][j] == J[i][j] && R[i][j] > 0)
            {
                if (mini > R[i][j])
                {
                    mini = R[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }
    fout << mini << ' ' << x + 1 << ' ' << y + 1;
    return 0;
}