Cod sursa(job #1582420)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 27 ianuarie 2016 21:50:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <fstream>
#include <string.h>
#include <queue>

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

const int Nmax = 105;

queue <pair<int, int> > Q1, Q2;

int n, m, R[Nmax][Nmax], J[Nmax][Nmax], Rix, Riy, Jix, Jiy, x[] = {-1,-1,0,1,1,1,0,-1}, y[] = {0,1,1,1,0,-1,-1,-1}, fx, fy, Time = 1000005;
char L[Nmax][Nmax];

void Read()
{
    f>>n>>m;
    f.get();
    for(int i = 1; i <= n; i++)
    {
        f.getline(L[i],101);
        for(int j = 0; j < m; j++)
        {
            if(L[i][j] == 'X') R[i][j+1] = J[i][j+1] = -1;
            if(L[i][j] == 'R') Rix = i, Riy = j+1;
            if(L[i][j] == 'J') Jix = i, Jiy = j+1;
        }
    }
    for(int i = 0; i <= n+1; i++)
            R[i][0] = J[i][0] = R[i][m+1] = J[i][m+1] = -1;
    for(int i = 0; i <= m+1; i++)
            R[0][i] = J[0][i] = R[n+1][i] = J[n+1][i] = -1;
    Q1.push(make_pair(Rix, Riy));
    Q2.push(make_pair(Jix, Jiy));
}

void Solve()
{
    int Rip, Riv, Rjp, Rjv, Jip, Jjp, Jiv, Jjv;
    while(!Q1.empty())
    {
        Rip = Q1.front().first;
        Rjp = Q1.front().second;
        Q1.pop();
        for(int i = 0; i < 8; i++)
        {
            Riv = Rip + x[i];
            Rjv = Rjp + y[i];
            if(R[Riv][Rjv] == 0)
            {
                R[Riv][Rjv] = R[Rip][Rjp] + 1;
                Q1.push(make_pair(Riv, Rjv));
            }
        }
    }
    while(!Q2.empty())
    {
        Jip = Q2.front().first;
        Jjp = Q2.front().second;
        Q2.pop();
        for(int i = 0; i < 8; i++)
        {
            Jiv = Jip + x[i];
            Jjv = Jjp + y[i];
            if(J[Jiv][Jjv] == 0)
            {
                J[Jiv][Jjv] = J[Jip][Jjp] + 1;
                Q2.push(make_pair(Jiv, Jjv));
            }
        }
    }
    for(int i = 1; i <=n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(R[i][j] == J[i][j] && R[i][j] > 0 && R[i][j] <Time)
            {
                Time = R[i][j];
                fx = i;
                fy = j;
            }
        }
}

void Print()
{
    g<<Time+1<<' '<<fx<<' '<<fy<<'\n';
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}