Cod sursa(job #2124216)

Utilizator anamaria41Raicu Ana anamaria41 Data 7 februarie 2018 00:02:52
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <cstdio>
#include <queue>

#define f first
#define s second

using namespace std;

queue < pair <int, int> > qj, qr;
int dx[8]= {1,-1,0,0,-1,-1,1,1};
int dy[8]= {0,0,1,-1,-1,1,-1,1};
int n,m,i,j, R[105][105],J[105][105];
int road, place_x, place_y;
char c;

void juli_lee()
{
    while ( !qj.empty() )
    {
        int l,c,ll,cc;
        l=qj.front().f;
        c=qj.front().s;
        qj.pop();
        for( int i=0; i<8; i++ )
        {
            ll=l+dx[i];
            cc=c+dy[i];
            if( J[ll][cc]==0 )
            {
                J[ll][cc]=J[l][c]+1;
                qj.push( make_pair(ll, cc ) );
            }
        }
    }
}

void rome_lee()
{
    while ( !qr.empty() )
    {
        int l,c,ll,cc;
        l=qr.front().f;
        c=qr.front().s;
        qr.pop();
        for( int i=0; i<8; i++ )
        {
            ll=l+dx[i];
            cc=c+dy[i];
            if( R[ll][cc]==0  )
            {
                R[ll][cc]=R[l][c]+1;
                qr.push( make_pair(ll, cc ) );
            }
        }
    }
}

int main()
{
    freopen ( "rj.in", "r", stdin );
    freopen ( "rj.out", "w", stdout );

    scanf ("%d%d", &n, &m);

    for( i=1; i<=n; i++ )
    {
        scanf( "%c", &c);

            for( j=1; j<=m; j++ )
            {
                scanf( "%c", &c);
                if ( c == ' ' ) R[i][j]=J[i][j]=0;
                else if ( c == 'X' ) R[i][j]=J[i][j]=-1;
                else if ( c == 'R' )
                {
                    R[i][j]=1, qr.push( make_pair( i, j ) );
                }
                else if ( c == 'J' )
                {
                    J[i][j]=1;
                    qj.push( make_pair( i, j ) );
                }
            }

    }

    for( i=0; i<=n+1; i++ ) J[i][0]=J[i][m+1]=R[i][0]=R[i][m+1]=-1;
    for( j=0; j<=m+1; j++ ) J[0][j]=J[n+1][j]=R[0][j]=R[n+1][j]=-1;


    juli_lee();
    rome_lee();



    road=1e9;

    for ( i=1; i<=n; i++ )
        for ( j=1; j<=m; j++)
            if ( R[i][j] > 0 && J[i][j]>0 )
                if ( R[i][j] == J[i][j])
                {
                    if ( road > R[i][j] )
                    {
                        road = R[i][j];
                        place_x = i;
                        place_y = j;
                    }

                }


    printf ( "%d %d %d\n", road, place_x, place_y );

    return 0;
}