Cod sursa(job #2352216)

Utilizator ViAlexVisan Alexandru ViAlex Data 23 februarie 2019 09:40:22
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <iostream>
#include<fstream>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
string valori[100];
int distante1[100][100];
int distante2[100][100];
int m,n;
struct pos
{
    int x;
    int y;
    pos operator+(pos&other)
    {
        pos a;
        a.x=x+other.x;
        a.y=y+other.y;
        return a;
    }
    pos()
    {
        x=0;
        y=0;
    }
    pos(int xp,int yp)
    {
        x=xp;
        y=yp;
    }
};
struct nod
{
    pos positie;
    int distanta;
};
bool e_valid(pos positie)
{
    return positie.x>=0 &&positie.x<n&&positie.y>=0 &&positie.y<m;
}
struct lista_noduri
{
    nod noduri[100000];
    int lista_inceput=0;
    int lista_final=1;

};

pos rpos;
pos jpos;
pos directii[8] {pos(1,0),pos(-1,0),pos(0,1),pos(0,-1),pos(1,1),pos(-1,-1),pos(-1,1),pos(1,-1)};
lista_noduri l1;
lista_noduri l2;


void lee_for(lista_noduri&l,int distante[100][100])
{
    nod primul=l.noduri[l.lista_inceput];
    int val=primul.distanta;
    pos aici=primul.positie;
    if(distante[aici.y][aici.x]>val ||!distante[aici.y][aici.x])
    {
        distante[aici.y][aici.x]=val;
        for(int i=0; i<8; i++)
        {
            pos newp=aici+directii[i];
            if(e_valid(newp)&&valori[newp.y][newp.x]==' ')
            {
                nod c;
                c.distanta=val+1;
                c.positie=newp;
                l.noduri[l.lista_final]=c;
                l.lista_final++;
            }
        }
    }
    l.lista_inceput++;
}
void prt(int mat[100][100])
{
    for(int i=0; i<m; i++)
    {
        for(int k=0; k<n; k++)
            cout<<mat[i][k]<<" ";
        cout<<endl;
    }
    cout<<endl<<endl;

}
void lee1()
{

    l1.noduri[0].positie=rpos;
    l1.noduri[0].distanta=0;
    while(l1.lista_final!=l1.lista_inceput)
        lee_for(l1,distante1);

}
void lee2()
{

    l2.noduri[0].positie=jpos;
    l2.noduri[0].distanta=0;
    while(l2.lista_final!=l2.lista_inceput)
        lee_for(l2,distante2);

}

void citire()
{
    in>>m>>n;
    string aux;
    getline(in,aux);
    for(int i=0; i<m; i++)
    {
        getline(in,valori[i]);
    }
    for(int i=0; i<m; i++)
    {
        for(int k=0; k<n; k++)
        {
            if(valori[i][k]=='R')
            {
                rpos.x=k;
                rpos.y=i;
            }
            else if(valori[i][k]=='J')
            {
                jpos.x=k;
                jpos.y=i;
            }
        }
    }
}
void evaluate()
{
    int minx=99999;
    pos min_pos;
    for(int i=0; i<m; i++)
    {
        for(int k=0; k<n; k++)
        {
            if(distante1[i][k]==distante2[i][k] &&distante1[i][k]<minx&& distante1[i][k])
            {
                minx=distante1[i][k];
                min_pos.x=k+1;
                min_pos.y=i+1;
            }
        }
    }
    out<<minx+1<<" ";
    out<<min_pos.y<<" "<<min_pos.x<<endl;


}
int main()
{
    citire();
    lee1();
    lee2();
    evaluate();
    return 0;
}