Cod sursa(job #467354)

Utilizator SpiderManSimoiu Robert SpiderMan Data 28 iunie 2010 14:51:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
# 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 ] ;
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 {
                    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;
}