Cod sursa(job #498737)

Utilizator DraStiKDragos Oprica DraStiK Data 5 noiembrie 2010 21:15:52
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <deque>
#include <fstream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef bool int01;
typedef char cha08;
typedef short int int16;
typedef int int32;
typedef float rea32;
typedef long long int int64;
typedef double rea64;

const cha08 Input[] = "rj.in";
const cha08 Output[] = "rj.out";

const int32 Dim = 105;
const int32 Inf = 0x3f3f3f3f;
const int32 dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int32 dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

cha08 h[Dim][Dim];
int32 N, M, XXX, XX, YY, X[2], Y[2];
int32 d[2][Dim][Dim];
queue < pair <int32, int32> > q;

int01 OK( int32 x, int32 y, int32 k ) {

    if( x < 1 || x > N )
        return 0;
    if( y < 1 || y > M )
        return 0;
    if( h[x][y] == 'X' )
        return 0;
    if( d[k][x][y] != -1 )
        return 0;

    return 1;
}

void BF( int32 k ) {

    int32 i, x, y;

    for( i = 1; i <= N; ++i )
        memset( d[k][i], -1, sizeof( d[k][i] ) );

    q.push( make_pair( X[k], Y[k] ) );
    d[k][X[k]][Y[k]] = 0;

    while( !q.empty() ) {

        x = q.front().first;
        y = q.front().second;
        q.pop();

        for( i = 0; i < 8; ++i )
            if( OK( x + dx[i], y + dy[i], k ) ) {

                d[k][x + dx[i]][y + dy[i]] = d[k][x][y] + 1;
                q.push( make_pair( x + dx[i], y + dy[i] ) );
            }
    }
}

int32 main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int32 i, j;

    fin >> N >> M;
    fin.ignore( 1, '\n' );

    for( i = 1; i <= N; ++i ) {

        fin.getline( h[i] + 1, Dim );
        for( j = 1; j <= M; ++j ) {

            if( h[i][j] == 'R' ) {

                X[0] = i;
                Y[0] = j;
            }
            if( h[i][j] == 'J' ) {

                X[1] = i;
                Y[1] = j;
            }
        }
    }

    BF( 0 );
    BF( 1 );

    XXX = Inf;
    for( i = 1; i <= N; ++i )
        for( j = 1; j <= M; ++j )
            if( d[0][i][j] != -1 && d[0][i][j] == d[1][i][j] && d[0][i][j] + 1 < XXX ) {

                XXX = d[0][i][j] + 1;
                XX = i;
                YY = j;
            }

    fout << XXX << " " << XX << " " << YY;

    fin.close();
    fout.close();

    return 0;
}