Cod sursa(job #2668043)

Utilizator CryshanaGanea Carina Cryshana Data 4 noiembrie 2020 13:23:14
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#define MAX 101
using namespace std;

ifstream in ("rj.in");
ofstream out ("rj.out");

int dR[MAX][MAX], dJ[MAX][MAX], coordi[] = {-1, -1, 0, 1, 1,  1,  0, -1};
int    N, M ,                   coordj[] = { 0,  1, 1, 1, 0, -1, -1, -1};
char h[MAX][MAX];

bool inside( int i, int j){
    return ( 1 <= i && i <= N ) && ( 1 <= j && j <= M);
}

int main(){

    in >> N >> M;

    queue<pair<int, int>> q;
    pair<int, int> J;

    string linie;
    getline(in, linie);

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

        getline(in, linie);
        for(int j = 1; j <= M; j++){
            if( linie.size() < j )
                h[i][j] = ' ';
            else
                h[i][j] = linie[j-1];
            if( h[i][j] == 'R'){
                q.push(make_pair(i,j));
                dR[i][j] = 1;
            }

            if( h[i][j] == 'J'){
                J = make_pair(i,j);
                dJ[i][j] = 1;
            }

        }
    }

    /*
    for( int i = 1; i <= N; i++){
        for( int j = 1; j <= M; j++)
            out << h[i][j];
        out << '\n';
    }
    */
    while( !q.empty()){
        int xi = q.front().first, xj = q.front().second;
        q.pop();

        for( int i = 0; i < 8; i++){
            int yi = xi+coordi[i], yj = xj+coordj[i];
            if( inside(yi, yj ) ){
                if( dR[yi][yj] == 0 && h[yi][yj] != 'X'){
                     q.push(make_pair(yi,yj));
                     dR[yi][yj] = dR[xi][xj] + 1;
                }
            }
        }
    }

    q.push(J);

    while( !q.empty()){
        int xi = q.front().first, xj = q.front().second;
        q.pop();

        for( int i = 0; i < 8; i++){
            int yi = xi+coordi[i], yj = xj+coordj[i];
            if( inside(yi, yj ) ){
                if( dJ[yi][yj] == 0 && h[yi][yj] != 'X'){
                     q.push(make_pair(yi,yj));
                     dJ[yi][yj] = dJ[xi][xj] + 1;
                }
            }
        }
    }

    int dmin = 201, pi, pj;

    for( int i = 1; i <= N; i++)
    for( int j = 1; j <= M; j++){
        if( dR[i][j] == dJ[i][j] && dR[i][j] < dmin && dR[i][j] != 0){
            dmin = dR[i][j];
            pi = i;
            pj = j;
        }

    }
    out << dmin << " " << pi << " " << pj;
    return 0;
}