Cod sursa(job #3130998)

Utilizator unomMirel Costel unom Data 18 mai 2023 23:06:59
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream in("rj.in");
ofstream out("rj.out");
int n, m;
int rom[103][103], jul[103][103];
int xr, yr, xj, yj;

int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};

void lee_rom(int istart, int jstart)
{
    queue<pair<int, int>> q;
    int i, j, iv, jv;

    rom[istart][jstart] = 1;
    q.push({istart, jstart});

    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;

        for(int k = 0; k<4; k++)
        {
            iv = i + di[k];
            jv = j + dj[k];

            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && rom[iv][jv] == 0)
            {
                rom[iv][jv] = rom[i][j] + 1;
                q.push({iv, jv});
            }
        }

        q.pop();
    }
}

void lee_jul(int istart, int jstart)
{
    queue<pair<int, int>> q;
    int i, j, iv, jv;

    jul[istart][jstart] = 1;
    q.push({istart, jstart});

    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;

        for(int k = 0; k<4; k++)
        {
            iv = i + di[k];
            jv = j + dj[k];

            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && jul[iv][jv] == 0)
            {
                jul[iv][jv] = jul[i][j] + 1;
                q.push({iv, jv});
            }
        }

        q.pop();
    }
}

int main()
{
    in>>n>>m;

    string s;
    getline(in, s);

    for(int i = 1; i<=n; i++)
    {
        getline(in, s);
        for(int j = 0; j<m; j++)
        {
            char c = s[j];

            if(c == ' ')
            {
                rom[i][j+1] = jul[i][j+1] = 0;
            }
            else if(c == 'X')
            {
                rom[i][j+1] = jul[i][j+1] = -1;
            }
            else if(c == 'R')
            {
                xr = i;
                yr = j+1;
            }
            else if(c == 'J')
            {
                xj = i;
                yj = j+1;
            }
        }
    }

    lee_rom(xr, yr);
    lee_jul(xj, yj);

    int tmin, x, y;
    tmin = 99999999;

    for(int i = 1; i<=n; i++)
    {
        for(int j = 1; j<=m; j++)
        {
            if(rom[i][j] == jul[i][j])
            {
                if(rom[i][j] > 1 && rom[i][j] < tmin)
                {
                    tmin = rom[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }

    out<<tmin - 1<<" "<<x<<" "<<y;



    return 0;
}