Cod sursa(job #1597445)

Utilizator RaresEGaySopterean Adrian RaresEGay Data 11 februarie 2016 23:33:11
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<fstream>
#include<queue>
#include<string.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

int Di[8] = {1,-1,0,0,1,-1,1,-1};
int Dj[8] = {0,0,1,-1,1,1,-1,-1};
int Map_Romeo[110][110], N, M;
int Map_Julieta[110][110];
int pi, pj, ui, uj;
queue < pair < int, int > > C;

bool Check_R(int i, int j){
    if(i<1 or i>N or j<1 or j>M)
        return false;
    if(Map_Romeo[i][j] == -1)
        return false;
    return true;
}

bool Check_J(int i, int j){
    if(i<1 or i>N or j<1 or j>M)
        return false;
    if(Map_Julieta[i][j] == -1)
        return false;
    return true;
}

void Read(){
    char s[110];
    fin >> N >> M;
    fin.getline(s,110);
    for (int i=1; i<=N; ++i){
        fin.getline(s,110);
        for(int j=0; j<M; ++j){
            if(s[j] == ' ')
                Map_Romeo[i][j+1] = 0;
            else if(s[j] == 'X')
                Map_Romeo[i][j+1] = -1;
            else if(s[j] == 'R'){
                pi = i; pj = j+1;
                Map_Romeo[i][j+1] = 1;
            }
            else if(s[j] == 'J'){
                ui = i; uj = j+1;
                Map_Romeo[i][j+1] = 0;
            }
        }
    }
}

void Lee_Romeo(){
    int i, j, Ni, Nj;
    C.push(make_pair(pi, pj));
    while(!C.empty() ){
        i = C.front().first;
        j = C.front().second;
        C.pop();
        for(int D=0; D<=7; ++D){
            Ni = i + Di[D];
            Nj = j + Dj[D];
            if(Check_R(Ni, Nj) and Map_Romeo[Ni][Nj] == 0){
                C.push(make_pair(Ni, Nj));
                Map_Romeo[Ni][Nj] = Map_Romeo[i][j] + 1;
            }
        }
    }
}

void Lee_Julieta(){
    int i, j, Ni, Nj;
    C.push(make_pair(ui, uj));
    while(!C.empty() ){
        i = C.front().first;
        j = C.front().second;
        C.pop();
        for(int D=0; D<=7; ++D){
            Ni = i + Di[D];
            Nj = j + Dj[D];
            if(Check_J(Ni, Nj) and Map_Julieta[Ni][Nj] == 0){
                C.push(make_pair(Ni, Nj));
                Map_Julieta[Ni][Nj] = Map_Julieta[i][j] + 1;
            }
        }
    }
}

void Comp(){
    int iC, jC, Min = 999999999;
    for(int i=1; i<=N; ++i)
        for(int j=1; j<=M; ++j){
            if(Map_Julieta[i][j] < Min and Map_Julieta[i][j] == Map_Romeo[i][j] and Map_Romeo[i][j] > 0 and Map_Julieta[i][j] > 0){
                    iC = i; jC = j;
                    Min = Map_Julieta[iC][jC];
                }
            }
        fout<<Map_Julieta[iC][jC]<<' '<<iC<<' '<<jC<<'\n';
}

int main(){
    Read();
    for(int i=1; i<=N; ++i)
        for(int j=1; j<=M; ++j)
            Map_Julieta[i][j] = Map_Romeo[i][j];
    Map_Julieta[pi][pj] = 0;
    Map_Julieta[ui][uj] = 1;
    Lee_Romeo();
    Lee_Julieta();
    Comp();
}