Cod sursa(job #2017309)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 31 august 2017 20:01:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>

using namespace std;

int n, m;
int rx, ry, jx, jy;
int dmin, fx, fy;
int romeo[102][102], julieta[102][102];
char aux[102];

int dx[8] = {-1, -1, 0, 1, 1,  1,  0, -1};
int dy[8] = { 0,  1, 1, 1, 0, -1, -1, -1};

bool OK( int x, int y, int arr[][102] ){

    if( x < 0 || y < 0 || x >= n || y >= m )
        return false;
    if( arr[x][y] != 0 )
        return false;

    return true;
}

void lee( int sx, int sy, int arr[][102] ){

    queue< pair<int, int> > coada;
    coada.push( make_pair(sx, sy) );
    arr[sx][sy] = 1;

    int x, y, x_next, y_next;

    while( !coada.empty() ){

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

        for(int d = 0; d < 8; d++){

            x_next = x + dx[d];
            y_next = y + dy[d];

            if( OK(x_next, y_next, arr) ){
                arr[x_next][y_next] = arr[x][y] + 1;
                coada.push( make_pair(x_next, y_next) );
            }
        }

    }

}

int main()
{
    ifstream in("rj.in");
    ofstream out("rj.out");

    in>>n>>m; in.get();

    for(int i = 0; i < n; i++){
        in.getline(aux, 101);
        for(int j = 0; j < m; j++){
            if( aux[j] == 'X' )
                romeo[i][j] = ( julieta[i][j] = -1);
            else if( aux[j] == 'R' ){
                rx = i; ry = j;
            }
            else if( aux[j] == 'J' ){
                jx = i; jy = j;
            }
        }
    }

    lee(rx, ry, romeo);
    lee(jx, jy, julieta);

    dmin = 10000000;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){

            if( romeo[i][j] != -1 && romeo[i][j] > 0 && julieta[i][j] != -1 && julieta[i][j] > 0){
                if( romeo[i][j] == julieta[i][j] ){
                    dmin = romeo[i][j] - 1;
                    fx = i + 1; fy = j + 1;
                }
            }

        }
    }

    out<<fx<<" "<<fx<<" "<<dmin;

    return 0;
}