Cod sursa(job #2124148)

Utilizator anamaria41Raicu Ana anamaria41 Data 6 februarie 2018 22:44:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 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, a[105][105], R[105][105],J[105][105];
int length, 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( a[ll][cc] == 0 && (J[ll][cc]==0 || J[ll][cc]==J[l][c] ))
            {
                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( a[ll][cc] == 0 && ( R[ll][cc]==0 || R[ll][cc]==R[l][c] ) )
            {
                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", &n, &m);

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

    }

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


    juli_lee();
    rome_lee();


    length=10000;

    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 ( length > R[i][j] )
                    {
                        length = R[i][j];
                        place_x = i;
                        place_y = j;
                    }
                    else if ( length == R[i][j] )
                        if( i < place_x)
                        {
                            place_x=i;
                            place_y=j;
                        }
                }


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

    return 0;
}