Cod sursa(job #2668626)

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

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

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


int m, x, y,nr,n,minim = 99999999;

int Romeo[101][101],Julieta[101][101];


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;

bool esteInMatrice ( int i, int j )
{
    return  i <= n && i >= 1 && j <= m && j >= 1 ;
}
void leeRomeo ( coordonate romeo )
{
    int i = romeo.x;
    int j = romeo.y;
    Romeo[i][j] = 1;
    Q1.push(romeo);
    while ( !Q1.empty() )
    {
        coordonate varf = Q1.front();
        Q1.pop();
        i = varf.x;
        j = varf.y;
        for ( int k = 1; k <= 8; k++ )
        {
            int ox = i + dx[k];
            int oy = j + dy[k];

            if ( esteInMatrice(ox,oy) && Romeo[ox][oy] == 0 )
            {
                Romeo[ox][oy] = Romeo[i][j] + 1;
                coordonate vecin;
                vecin.x = ox;
                vecin.y = oy;
                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 varf = Q2.front();
        Q2.pop();
        i = varf.x;
        j = varf.y;
        for ( int k = 1; k <= 8; k++ )
        {
            int ox = i + dx[k];
            int oy = j + dy[k];
            if ( esteInMatrice(ox,oy) && Julieta[ox][oy] == 0 )
            {
                Julieta[ox][oy] = Julieta[i][j] + 1;
                coordonate vecin;
                vecin.x = ox;
                vecin.y = oy;
                Q2.push(vecin);
            }
        }
    }
}

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

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

        for ( int j = 0; j <m; 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;
            }

        }
    }
    leeRomeo(romeo);
    leeJulieta(julieta);



    intalnire.x=-1, intalnire.y=-1;

    for ( int i = 1 ; i <= n ; i++ )
        for (int j = 1 ; j <= m ; j++ )
            if ( Romeo[i][j] == Julieta[i][j] && Romeo[i][j] < minim && Romeo[i][j] >0 )
            {
                minim = Romeo[i][j] ;
                intalnire.x= i ;
                intalnire.y = j ;
            }
    g << minim << " " <<   intalnire.x << " " << intalnire.y << endl;
    return 0;
}