Cod sursa(job #1329181)

Utilizator gedicaAlpaca Gedit gedica Data 29 ianuarie 2015 10:19:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <algorithm>
#include <fstream>
#include <deque>

using namespace std;

const int INF= ( 1<<30 ), NMAX= 100;
const int dx[] = {0, 1, 0, -1, -1, -1, 1, 1}, dy[] = {1, 0, -1, 0, -1, 1, 1, -1};

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

int R[NMAX+2][NMAX+2], J[NMAX+2][NMAX+2];
deque <int> qx, qy;

void ans( int N, int M )
{
    int x, y, tmin= INF;

    for( int i= 1; i<=N; ++i )
    {
        for( int j= 1; j<=M; ++j )
        {
            if( R[i][j] == J[i][j] && R[i][j] != -1 )
            {
                if( tmin > R[i][j] && R[i][j] != 0 )
                {
                    tmin= R[i][j];
                    x= i;
                    y= j;
                }
            }
        }
    }

    out << tmin << " " << x << " " << y;
}

void lee_R()
{
    int x, y;

    while( !qx.empty() )
    {
        x = qx.front();
        y = qy.front();

        qx.pop_front();
        qy.pop_front();

        for( int i= 0; i<8; ++i )
        {

            if( R[ x+dx[i] ][ y+dy[i] ] == 0 )
            {
                R[ x+dx[i] ][ y+dy[i] ] = R[x][y] + 1;
                qx.push_back( x+dx[i] );
                qy.push_back( y+dy[i] );
            }

        }
    }

}

void lee_J()
{
    int x, y;

    while( !qx.empty() )
    {
        x = qx.front();
        y = qy.front();

        qx.pop_front();
        qy.pop_front();

        for( int i= 0; i<8; ++i )
        {
            if( J[ x + dx[i] ][ y + dy[i] ] == 0 )
            {
                J[ x + dx[i] ][ y + dy[i] ] = J[x][y] + 1;
                qx.push_back( x + dx[i] );
                qy.push_back( y + dy[i] );
            }
        }
    }

}

int main()
{
    int N, M, Rx, Ry, Jx, Jy;
    char c;
    in >> N >> M;
    in.get(c);

    for( int i= 1; i<=N; ++i )
    {
        for( int j= 1; j<=M+1; ++j )
        {
            in.get(c);

            if( c == 'X' )
                R[i][j] = J[i][j] = -1;

            if( c == 'R' )
            {
                Rx = i;
                Ry = j;
                R[Rx][Ry] = 1;
            }

            if( c == 'J' )
            {
                Jx = i;
                Jy = j;
                J[Jx][Jy] = 1;
            }

            if( c == '\n' )
                j = INF;
        }
    }

    for(int i = 0; i <= M + 1; i++)
    {
        R[0][i] = R[N+1][i] = J[0][i] = J[N+1][i] = -1;
    }

    for(int i = 0; i <= N + 1; i++)
    {
        R[i][0] = R[i][M+1] = J[i][0] = J[i][M+1] = -1;
    }

    qx.push_back(Rx);
    qy.push_back(Ry);

    lee_R();

    qx.push_back(Jx);
    qy.push_back(Jy);

    lee_J();

    ans( N, M );

    return 0;
}