Cod sursa(job #2668486)

Utilizator florescu.mirunaMiruna Stefania Florescu florescu.miruna Data 4 noiembrie 2020 22:30:32
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.23 kb
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

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


int m,n,x,y, Romeo[105][105],Julieta[105][105],minim = 500000, loc_intalnire_x=-1, loc_intalnire_y=-1;
struct coordonate
{
    int x, y ;
} romeo,julieta;

///vectori care ma ajuta sa ma deplasez in matrice
int directie_x[]= {0, 0, 1, 0, -1, -1, 1, -1, 1};
int directie_y[]= {0, 1, 0, -1, 0, -1, 1,  1,-1};

queue < coordonate > Q1,Q2;

///Functie care verifica daca ies din matrice
bool esteInMatrice ( int i, int j )
{
    return  i <= n && j <= m && i >= 1  && j >= 1 ;
}
void leeRomeo ( coordonate romeo )
{
    ///Pornesc din locul in care se afla Romeo initial

    int i = romeo.x;
    int j = romeo.y;

    Romeo[i][j] = 1;
    Q1.push(romeo);

    while ( !Q1.empty() ) ///Cat timp coada nu este vida inseamna ca inca mai am unde sa ma duc in matrice
    {
        coordonate loc = Q1.front();
        Q1.pop();

        i = loc.x;
        j = loc.y;

        ///Verific vecinii in toate directiile: sus,jos,stanga, dreapta si pe cei de pe diagonale

        for ( int k = 1; k <= 8; k++ )
        {
            int vecin_x = i + directie_x[k]; ///Salvez coordonatele vecinilor
            int vecin_y = j + directie_y[k];

            if ( esteInMatrice(vecin_x,vecin_y) && Romeo[vecin_x][vecin_y] == 0 )

                ///Verific daca locul pe care vreau sa merg nu este un obstacol si ma asigur ca nu ies din matrice
            {
                Romeo[vecin_x][vecin_y] = Romeo[i][j] + 1;
                ///In matrice va ramane salvat lungimea drumului din locul de plecare pana in locul curent

                coordonate vecin;
                vecin.x = vecin_x;
                vecin.y = vecin_y;

                ///Introduc in coada vecinii
                Q1.push(vecin);
            }
        }
    }
}
void leeJulieta ( coordonate julieta )
{
    int i = julieta.x;
    int j = julieta.y;

    Julieta[i][j] = 1;

    Q2.push(julieta);
    while ( !Q2.empty() )
    {
        coordonate loc = Q2.front();
        Q2.pop();
        i = loc.x;
        j = loc.y;
        for ( int k = 1; k <= 8; k++ )
        {
            int vecin_x = i + directie_x[k];
            int vecin_y = j + directie_y[k];
            if ( esteInMatrice(vecin_x,vecin_y) && Julieta[vecin_x][vecin_y] == 0 )
            {
                Julieta[vecin_x][vecin_y] = Julieta[i][j] + 1;

                coordonate vecin;
                vecin.x = vecin_x;
                vecin.y = vecin_y;
                Q2.push(vecin);
            }
        }
    }
}

char linie[105];
int main()
{
    f >> n >> m;
    f.get();

    for(int i = 1; i <= n; i++)
    {
        f.getline(linie,105);
        ///In matrici vom marca cu -1 obstacolele
        ///iar unde este spatiu de trecere va ramane 0 doarece matricile sunt declarate global

        for ( int j = 1; j <= m; j++ )
        {

            if ( linie[j-1] == 'X' )
                Romeo[i][j]  = Julieta[i][j] = -1;

            ///Salvez coordonatele lui Romeo

            if ( linie[j-1] == 'R' )
            {

                romeo.x = i;
                romeo.y = j;
                Julieta[i][j] = -1;
            }
            ///Salvez coordonatele Julietei

            if ( linie[j-1] == 'J' )
            {

                julieta.x = i;
                julieta.y = j;
                Romeo[i][j] = -1;
            }

        }
    }


    ///Facem 2 Lee-uri separate pentru Romeo si Julieta
    ///Avem o matrice in care sunt salvate drumurile lui Romeo si una cu drumurile Julietei

    leeRomeo(romeo);
    leeJulieta(julieta);



    for ( int i = 1 ; i <= n ; i++ )
        for (int j = 1 ; j <= m ; j++ )
            if ( Romeo[i][j] == Julieta[i][j] &&  Romeo[i][j] >0 )
    ///Caut locul de intalnire, adica locul pana unde fiecare a parcurs aceeasi distanta, iau cea mai mica valoare pe care o gasesc
            {

                minim = Romeo[i][j] ;
                loc_intalnire_x = i ;
                loc_intalnire_y = j ;
            }
    g << minim << ' ' << loc_intalnire_x << ' ' << loc_intalnire_y << endl;
    return 0;
}