Cod sursa(job #466613)

Utilizator SpiderManSimoiu Robert SpiderMan Data 27 iunie 2010 11:58:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
# include <cstdio>
# include <queue>
using namespace std;

# define ii first
# define jj second

typedef pair < int, int > PR;
const char FIN[] = "rj.in", FOU[] = "rj.out";
const int MAX = 105 , oo = 0x3f3f3f3f ;
const int dx[] = { -1 , -1 , 0 , 1 , 1 ,  1 ,  0 , -1 } ;
const int dy[] = {  0 ,  1 , 1 , 1 , 0 , -1 , -1 , -1 } ;

PR R, J ;
bool V[ MAX ][ MAX ], RO[ MAX ][ MAX ], JU[ MAX ][ MAX ] ;
int RM[ MAX ][ MAX ] , JL [ MAX ][ MAX ] ;
int N, M ;
char S[ MAX ] ;

void read_data ()
{
    scanf ( "%d %d\n", &N, &M ) ;

    for (int i = 1; i <= N; ++i)
    {
        fgets ( S + 1, MAX, stdin ) ;

        for (int j = 1; j <= M; ++j)
        {
            if ( S[j] == 'X' )
                V[i][j] = 1;
            else if ( S[j] == 'J' )
                J = make_pair ( i, j ) ;
            else if ( S[j] == 'R' )
                R = make_pair ( i, j ) ;
        }
    }
}

void solve ( int A[ MAX ][ MAX ], PR B )
{
    bool VIZ[ MAX ][ MAX ] ;
    queue < PR > Q ;

    memset ( VIZ, 0, sizeof ( VIZ ) ) ;
    Q.push ( B ) , VIZ[ B.ii ][ B.jj ] = 1 ;

    while ( ! Q.empty () )
    {
        PR rec = Q.front () ;
        Q.pop () ;

        for ( int k = 0; k < 8; ++k )
        {
            PR act = rec ;
            act.ii += dx[k] , act.jj += dy[k] ;

            if ( act.ii > 0 && act.ii <= N && act.jj > 0 && act.jj <= M )
                if ( VIZ[ act.ii ][ act.jj ] == 0 && V[ act.ii ][ act.jj ] == 0 )
                {
                    A[ act.ii ][ act.jj ] = A[ rec.ii ][ rec.jj ] + 1 ;
                    VIZ[ act.ii ][ act.jj ] = 1;
                    Q.push ( make_pair ( act.ii, act.jj ) ) ;
                }
        }
    }
}

void write_data ()
{
    int min = oo, i1 = oo, j1 = oo ;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            if ( RM[ i ][ j ] == JL[ i ][ j ] && RM[ i ][ j ] <= min && RM[ i ][ j ] > 0 )
                if ( RM[ i ][ j ] == min )
                    if ( i1 > i || i1 == i && j1 > j ) i1 = i, j1 = j ;
                    else ;
                else min = RM[ i ][ j ], i1 = i, j1 = j;

    printf ( "%d %d %d", ++min, i1, j1 ) ;
}
int main()
{
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    read_data () ;
    solve ( JL, J ), solve ( RM , R ) ;
    write_data () ;

    return 0;
}