Cod sursa(job #2666693)

Utilizator anamaria2602Avram Ana Maria anamaria2602 Data 2 noiembrie 2020 13:35:55
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.09 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

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

int nr, n;
char C;
int m, x, y;
int a[176][176],R[101][101],J[101][101];

struct pereche
{
    int x, y ;
} start,stop;

int dx[]= {0, 0, 1, 0, -1, -1, 1, -1, 1};
int dy[]= {0, 1, 0, -1, 0, -1, 1,  1,-1};

queue < pereche > Q,T;

int interior ( int i, int j )
{
    return  i <= n and i >= 1 and j <= m and j >= 1 ;//daca se afla in matrice
}
void leeR ( pereche start )
{
    int i = start.x;
    int j = start.y;
    R[i][j] = 1;
    Q.push(start); // adaug in coada
    while ( !Q.empty() ) // cat timp coada nu este vida
    {
        pereche varf = Q.front();
        Q.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 ( interior(ox,oy) and R[ox][oy] == 0 ) // daca vecinul se afla in matrice si pot ajunge la el
            {
                R[ox][oy] = R[i][j] + 1;
                pereche vecin;
                vecin.x = ox;
                vecin.y = oy;
                Q.push(vecin); // bag vecinii in coada
            }
        }
    }
}
void leeJ ( pereche stop )
{
    int i = stop.x;
    int j = stop.y;
    J[i][j] = 1;
    T.push(stop); // adaug in coada
    while ( !T.empty() ) // cat timp coada nu este vida
    {
        pereche varf = T.front();
        T.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 ( interior(ox,oy) and J[ox][oy] == 0 ) // daca vecinul se afla in matrice si pot ajunge la el
            {
                J[ox][oy] = J[i][j] + 1;
                pereche vecin;
                vecin.x = ox;
                vecin.y = oy;
                T.push(vecin); // bag vecinii in coada
            }
        }
    }
}

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

    for(int i = 1; i <= n; i++)
    {
        f.getline(s,101);
        /// g << s <<endl;
        for ( int j = 1; j <= m; j++ )
        {
            if ( s[j-1] == 'X' )
            {
                //marchez obstacolele
                R[i][j] = -1;
                J[i][j] = -1;
            }
            else if ( s[j-1] == 'R' )
            {
                //aflam coordonatele lui Romeo
                start.x = i;
                start.y = j;
                R[i][j] = 0;
                J[i][j] = -1;
            }
            else if ( s[j-1] == 'J' )
            {
                //aflam coordonatele Julietei
                stop.x = i;
                stop.y = j;
                J[i][j] = 0;
                R[i][j] = -1;
            }
            else
            {
                //altfell este zona de trecere
                R[i][j] = 0;
                J[i][j] = 0;
            }
        }
    }
    leeR(start); //aflam distantele minime pentru cazul in care se pleaca din coordonatele lui Romeo si se ajunge la cele ale Julietei
    leeJ(stop); //aflam distantele minime pentru cazul in care se pleaca din coordonatele Julietei si se ajunge la cele ale lui Romeo

    /// for(int i=1; i<=n; i++ and g<<endl) //afisam matricea lui Romeo
        /// for(int j=1; j<=m; j++)
            /// g<<R[i][j]<<" ";
    /// for(int i=1; i<=n; i++ and g<<endl) //afisam matricea Julietei
        /// for(int j=1; j<=m; j++)
            /// g<<J[i][j]<<" ";
    int minim = 99999999, ox=-1, oy=-1;
    for ( int i = 1 ; i <= n ; i++ )
        for (int j = 1 ; j <= m ; j++ )
            if ( R[i][j] == J[i][j] and R[i][j] < minim and R[i][j] >0 ) ///daca s-a parcurs un nr egal de pasi si e minima distanta
            {
                minim = R[i][j] ;
                ox = i ;
                oy = j ;
            }
    g << minim << ' ' << ox << ' ' << oy << endl;
    return 0;
}