Cod sursa(job #1923383)

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

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

int di[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dj[] = {1, -1, 0, 0, 1, -1, 1, -1};

int MapRomeo[100][100];
int MapJulieta[100][100];
int N, M,i,j;

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

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

void LeeR()
{
    int i,j,next_i,next_j;
    while( !coadaR.empty() ) // Lucreaza atata timp cat sunt puncte la coada
    {
        i=coadaR.front().first; // i extrage coordonata x a primului punct din coada
        j=coadaR.front().second;// j extrage coordonata y a primului punct din coada
        coadaR.pop(); // sterge primul punct din coada

        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 LeeJ()
{
    int i,j,next_i,next_j;
    while( !coadaJ.empty() ) // Lucreaza atata timp cat sunt puncte la coada
    {
        i=coadaJ.front().first; // i extrage coordonata x a primului punct din coada
        j=coadaJ.front().second;// j extrage coordonata y a primului punct din coada
        coadaJ.pop(); // sterge primul punct din coada

        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=600, x,y;
    fin>>N>>M;
    char c;
    fin.get(c);
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            fin.get(c);
            if(c == 'X')
            {
                MapRomeo[i][j] = -1;
                MapJulieta[i][j] = -1;
            }
            else if(c == 'R')
            {
                MapRomeo[i][j]=1;
                MapJulieta[i][j]=0;
                coadaR.push(make_pair(i,j));
            }
            else if(c == 'J')
            {
                MapRomeo[i][j]=0;
                MapJulieta[i][j]=1;
                coadaJ.push(make_pair(i,j));
            }
            else
            {
                MapRomeo[i][j]=0;
                MapJulieta[i][j]=0;
            }
        }
        fin.get(c);
    }
    LeeJ();
    LeeR();

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {

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