Cod sursa(job #1923400)

Utilizator PRaduPoza Radu PRadu Data 10 martie 2017 23:40:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include<fstream>
#include<queue>
using namespace std;

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

int MapRomeo[100][100];
int MapJulieta[100][100],i,j;
int N,M;
int di[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dj[] = {1, -1, 0, 0, 1, -1, 1, -1};

queue < pair<int, int> > coadaR;
queue < pair<int, int> > coadaJ;


bool OK(int i, int j){
    if(i<1 || j<1)
        return false;
    if(i>N || j>M)
        return false;
    return true;
}

void LeeRomeo(){
    int i, j, next_i, next_j;
    while( !coadaR.empty() )
    {
        i = coadaR.front().first;
        j = coadaR.front().second;
        coadaR.pop();
        for(int directie=0; directie<8; directie++)
        {
            next_i = i + di[directie];
            next_j = j + dj[directie];
            if(OK(next_i, next_j) && MapRomeo[next_i][next_j] == 0)
            {
                MapRomeo[next_i][next_j] = MapRomeo[i][j] + 1;
                coadaR.push(make_pair(next_i, next_j));
            }
        }
    }
}

void LeeJulieta(){
    int i, j, next_i, next_j;
    while( !coadaJ.empty() )
    {
        i = coadaJ.front().first;
        j = coadaJ.front().second;
        coadaJ.pop();
        for(int directie=0; directie<8; directie++)
        {
            next_i = i + di[directie];
            next_j = j + dj[directie];
            if(OK(next_i, next_j) && MapJulieta[next_i][next_j] == 0)
            {
                MapJulieta[next_i][next_j] = MapJulieta[i][j] + 1;
                coadaJ.push(make_pair(next_i, next_j));
            }
        }
    }
}


int main(){
    int tmin=10000,x,y;
    fin>>N>>M;
    char c;
    fin.get(c);
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            fin.get(c);
            if(c == 'R')
            {
                MapRomeo[i][j] = 1;
                MapJulieta[i][j] = 0;
                coadaR.push(make_pair(i, j));
            }
            if(c == 'J')
            {
                MapRomeo[i][j] = 0;
                MapJulieta[i][j] = 1;
                coadaJ.push(make_pair(i, j));
            }
            if(c == 'X')
            {
                MapRomeo[i][j] = -1;
                MapJulieta[i][j] = -1;
            }
            if(c == ' ')
            {
                MapRomeo[i][j] = 0;
                MapJulieta[i][j] = 0;
            }
        }
        fin.get(c);
    }


    LeeRomeo();
    LeeJulieta();

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            if(MapRomeo[i][j] == MapJulieta[i][j] && MapRomeo[i][j]>0 && MapRomeo[i][j] < tmin)
            {
                tmin = MapRomeo[i][j];
                x=i;
                y=j;
            }
        }
    }
    fout<<tmin<<' '<<x<<' '<<y;
    return 0;
}