Cod sursa(job #2153779)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 6 martie 2018 14:15:00
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <fstream>
#include <queue>

using namespace std;

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

int n, m, minim, x_minim, y_minim;
int R[105][105], rx, ry, J[105][105], jx, jy;
char linie[105];

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

bool OK( int x, int y, int a[][105] )
{
    if( x < 1 || y < 1 || x >= n || y >= m )
        return false;

    if( a[x][y] != 0 )
        return false;

    return true;
}

void lee( int sx, int sy, int a[][105] )
{
    queue< pair<int, int> > coada;
    coada.push( make_pair(sx, sy) );
    int xc, yc, xn, yn;

    while( !coada.empty() )
    {
        xc = coada.front().first;
        yc = coada.front().second;
        coada.pop();

        for( int i = 0; i <= 7; i++ )
        {
            xn = xc + dx[i];
            yn = yc + dy[i];

            if( OK( xn, yn, a ) )
            {
                a[xn][yn] = a[xc][yc] + 1;
                coada.push( make_pair(xn, yn) );
            }
        }
    }
}

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

    for( int i = 1; i <= n; i++ )
    {
        in.getline( linie, 104, '\n' );

        for( int j = 0; j < m; j++ )
            if( linie[j] == 'X' )
                R[i][j + 1] = J[i][j + 1] = -1;
            else if( linie[j] == 'R' )
            {
                R[i][j + 1] = 1;
                rx = i;
                ry = j + 1;
            }
            else if( linie[j] == 'J' )
            {
                J[i][j + 1] = 1;
                jx = i;
                jy = j + 1;
            }
    }

    lee( rx, ry, R );
    lee( jx, jy, J );

    minim = 0x7fffffff;

    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= m; j++ )
            if( R[i][j] > 0 && R[i][j] == J[i][j] )
                if( minim > R[i][j] )
                {
                    minim = R[i][j];
                    x_minim = i;
                    y_minim = j;
                }

    out<<minim<<" "<<x_minim<<" "<<y_minim;

    return 0;
}