Cod sursa(job #1597420)

Utilizator alinp25Alin Pisica alinp25 Data 11 februarie 2016 23:12:42
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.1 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>

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

int MapRomeo[128][128]; //Harta Romeo
int MapJulieta[128][128]; //Harta Julieta
int n, m; //Linii, Coloane
int romeoI, romeoJ, julietaI, julietaJ; //Coordonate Romeo, Julieta
std::queue <std::pair < int, int > > Coada; //Coada
const int di[] = {0, 0, 1, -1, 1, 1, -1, -1}; //Deplasare pe i
const int dj[] = {1, -1, 0, 0, 1, -1, 1, -1}; //Deplasare pe j
int coord_i, coord_j, coord_timp = (int)2e9; //Coordonatele finale si timpul dupa care se intalnesc

bool okRomeo(int x, int y) //Verificarea celulei daca este libera
{
    if (x < 0 || y < 0 || x >= n || y >= m)
        return false;
    if (MapRomeo[x][y] == -1)
        return false;
    return true;
}

bool okJulieta(int x, int y)
{
    if (x < 0 || y < 0 || x >= n || y >= m)
        return false;
    if (MapJulieta[x][y] == -1)
        return false;
    return true;
}

void LeeJulieta()
{
    int i, j, iUrmator, jUrmator;
    MapJulieta[julietaI][julietaJ] = 1; //Plec de la pozitia Julietei
    Coada.push(std::make_pair(julietaI, julietaJ)); //Adaug pozitia Julietei in coada
    while (!Coada.empty()) //Cat timp coada e goala
    {
        i = Coada.front().first; //Extrag coordonata i a primului element din coada
        j = Coada.front().second; //Extrag coordonata j a primului element din coada
        Coada.pop(); //Elimin elementul din coada
        for (int directie = 0; directie < 8; directie++) //Verific toate pozitiile alaturate
        {
            iUrmator = i + di[directie]; //Coordonata i a pozitiei urmatoare
            jUrmator = j + dj[directie]; //Coordonata j a pozitiei urmatoare
            if (okJulieta(iUrmator, jUrmator) && MapJulieta[iUrmator][jUrmator] == 0) //Verific daca e o mutare valida
            {
                MapJulieta[iUrmator][jUrmator] = MapJulieta[i][j] + 1; //Incrementez valoarea pozitiei urmatoare
                Coada.push(std::make_pair(iUrmator, jUrmator)); //Adaug in coada
            }
        }
    }
}

void LeeRomeo()
{
    int i, j, iUrmator, jUrmator;
    MapRomeo[romeoI][romeoJ] = 1; //Plec de la pozitia lui Romeo
    Coada.push(std::make_pair(romeoI, romeoJ)); //Adaug pozitia lui Romeo in coada
    while (!Coada.empty()) //Cat timp coada e goala
    {
        i = Coada.front().first; //Extrag coordonata i a primului element din coada
        j = Coada.front().second; //Extrag coordonata j a primului element din coada
        Coada.pop(); //Elimin elementul din coada
        for (int directie = 0; directie < 8; directie++) //Verific toate pozitiile alaturate
        {
            iUrmator = i + di[directie]; //Coordonata i a pozitiei urmatoare
            jUrmator = j + dj[directie]; //Coordonata j a pozitiei urmatoare
            if (okRomeo(iUrmator, jUrmator) && MapRomeo[iUrmator][jUrmator] == 0) //Verific daca e o mutare valida
            {
                MapRomeo[iUrmator][jUrmator] = MapRomeo[i][j] + 1; //Incrementez valoarea pozitiei urmatoare
                Coada.push(std::make_pair(iUrmator, jUrmator)); //Adaug in coada
            }
        }
    }
}

void Read() //Construirea hartii
{
    fin >> n >> m; //Citesc liniile si coloanele
    std::string aux;
    std::getline(fin, aux, '\n'); //Trec la matrice
    for (int i = 0; i < n; i++) //Parcurg liniile
    {
        std::getline(fin, aux, '\n'); //Citesc o intreaga liniile
        for (int j = 0; j < m; j++) //Parcurg fiecare coloana
        {
            if (aux[j] == 'R')
            {
                //Initializez coordonatele lui Romeo
                romeoI = i;
                romeoJ = j;
                //Initializez valoarea pozitiei
                MapRomeo[i][j] = 0;
                MapJulieta[i][j] = 0;
            }
            else if (aux[j] == 'J')
            {
                //Initializez coordonatele Julietei
                julietaI = i;
                julietaJ = j;
                //Initializez valoarea pozitiei
                MapRomeo[i][j] = 0;
                MapJulieta[i][j] = 0;
            }
            else if (aux[j] == 'X')
            {
                MapRomeo[i][j] = -1;
                MapJulieta[i][j] = -1;
            }
            else
            {
                MapRomeo[i][j] = 0;
                MapJulieta[i][j] = 0;
            }
        }
    }
}

void Cautare()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if ((MapRomeo[i][j] == MapJulieta[i][j]) && MapRomeo[i][j] > 0)
            {
                if (coord_timp >= MapRomeo[i][j] - 1)
                {
                    coord_timp = MapRomeo[i][j] - 1;
                    coord_i = i + 1;
                    coord_j = j + 1;
                }
            }
        }
    }
    fout << coord_i << " " << coord_j << " " << coord_timp;
}

int main(int argc, char *argv[])
{
    Read(); //Construieste harta
    LeeRomeo(); //Parcurere Lee pentru Romeo
    LeeJulieta(); //Parcurgere Lee pentru Julieta
    Cautare();
    return 0;
}