Cod sursa(job #2668624)

Utilizator florescu.mirunaMiruna Stefania Florescu florescu.miruna Data 5 noiembrie 2020 05:16:53
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <iostream>
#include <fstream>
#include<string>
#include<cstring>
#include <queue>
using namespace std;

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

int n,m,x,y,Julieta[105][105],Romeo[105][105],minim = 99999999;
char linie[105];

struct coordonate
{
    int x,y;
} romeo,julieta,intalnire;


int dx[]= {0, 0, 1, 0, -1, -1, 1, -1, 1};
int dy[]= {0, 1, 0, -1, 0, -1, 1,  1,-1};
queue <coordonate> Q1,Q2;

void leeRomeo ( coordonate start )
{
    int i = start.x;
    int j = start.y;
    Romeo[i][j] = 1;
    Q1.push(start); /// adaug in coada
    while ( !Q1.empty() ) /// cat timp coada nu este vida
    {
        coordonate varf = Q1.front();
        Q1.pop();
        i = varf.x;
        j = varf.y; /// extrag din coada varful cozii

        for ( int k = 1; k <= 8; k++ )
        {
            int ox = i + dx[k];
            int oy = j + dy[k]; ///coordonatele vecinilor
            if ( Romeo[ox][oy] == 0 ) /// daca vecinul se afla in matrice si pot ajunge la el
            {
                Romeo[ox][oy] = Romeo[i][j] + 1;
                coordonate vecin;
                vecin.x = ox;
                vecin.y = oy;
                Q1.push(vecin); /// bag vecinii in coada
            }
        }
    }

}


void leeJulieta ( coordonate start )
{
    int i = start.x;
    int j = start.y;
    Julieta[i][j] = 1;
    Q2.push(start);
    while ( !Q2.empty() )
    {
        coordonate varf = Q2.front();
        Q2.pop();
        i = varf.x;
        j = varf.y; /// extrag din coada varful cozii

        for ( int k = 1; k <= 8; k++ )
        {
            int ox = i + dx[k];
            int oy = j + dy[k]; ///coordonatele vecinilor
            if ( Julieta[ox][oy] == 0 ) /// daca vecinul se afla in matrice si pot ajunge la el
            {
                Julieta[ox][oy] = Julieta[i][j] + 1;
                coordonate vecin;
                vecin.x = ox;
                vecin.y = oy;
                Q2.push(vecin); /// bag vecinii in coada
            }
        }
    }

}

int main()
{
    f>>n>>m;
    f.get();
    intalnire.x = -1;
    intalnire.y = -1;

    for(int i=1; i<=n; i++)
    {
        f.getline(linie,101);
        for(int j=0; j<n; j++)
        {


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

            }
            if(linie[j] == 'R')
            {
                romeo.x = i;
                romeo.y = j+1;
                Julieta[i][j+1] = -1;
            }


            if(linie[j] == 'J')
            {
                julieta.x = i;
                julieta.y = j+1;
                Romeo[i][j+1] = -1;
            }


        }
    }



    for (int i = 0; i <= m + 1; i++)
        Romeo[0][i] = Romeo[n + 1][i] =  Julieta[0][i] = Julieta[n + 1][i] = -1;

    for (int i = 0; i <= n + 1; i++)
        Romeo[i][0] = Romeo[i][m + 1] =  Julieta[i][0] = Julieta[i][m + 1] = -1;


    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]  )
                if( Julieta[i][j]!= -1 && Julieta[i][j]!= 0)
                    if (Julieta[i][j] < minim)
                    {
                        minim = Julieta[i][j];
                        intalnire.x = i;
                        intalnire.y = j;
                    }

        }
    g<<minim<<" "<<intalnire.x<<" "<<intalnire.y;
    return 0;
}