Cod sursa(job #2581248)

Utilizator TitoxykBuruiana Stefan Titoxyk Data 14 martie 2020 19:09:20
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <queue>
#include <cstring>


using namespace std;

ifstream cin("rj.in");
ofstream cout("rj.out");

struct poz
{
    int x;
    int y;
};

struct oras
{
    bool valabil;
    int tromeo=999999999;
    int tjulieta=999999999;
}v[101][101];

queue <poz> c;
queue <poz> c2;

poz romeo;
poz julieta;

char t;
char a[1001];

int n,m;

int x[9]={0,-1,-1,0,1,1,1,0,-1};
int y[9]={0,0,1,1,1,0,-1,-1,-1};

bool valid_poz(poz a,int n,int m)
{
    if(v[a.x][a.y].valabil==0)return false;
    if(a.x>0 and a.x<=n and a.y>0 and a.y<=m)return true;
    return false;
}

int main()
{
    cin>>n>>m;
    cin.get();
    for(int i=1;i<=n;i++)
    {
        cin.getline(a,1000);
        for(int j=1;j<=m;j++)
        {
            t=a[j-1];
            if(t=='X')v[i][j].valabil=0;
            else v[i][j].valabil=1;
            if(t=='R')romeo.x=i,romeo.y=j;
            if(t=='J')julieta.x=i,julieta.y=j;
        }
    }
    c.push(romeo);
    v[romeo.x][romeo.y].tromeo=0;
    while(c.size())
    {
        poz aux=c.front();
        c.pop();
        for(int i=1;i<=8;i++)
        {
            poz new_poz;
            new_poz.x=aux.x+x[i];
            new_poz.y=aux.y+y[i];
            if(valid_poz(new_poz,n,m) and v[new_poz.x][new_poz.y].tromeo>v[aux.x][aux.y].tromeo+1)v[new_poz.x][new_poz.y].tromeo=v[aux.x][aux.y].tromeo+1,c.push(new_poz);
        }
    }
    while(c.size())c.pop();
    c.push(julieta);
    v[julieta.x][julieta.y].tjulieta=0;
    while(c.size())
    {
        poz aux=c.front();
        c.pop();
        for(int i=1;i<=8;i++)
        {
            poz new_poz;
            new_poz.x=aux.x+x[i];
            new_poz.y=aux.y+y[i];
            if(valid_poz(new_poz,n,m) and v[new_poz.x][new_poz.y].tjulieta>v[aux.x][aux.y].tjulieta+1)v[new_poz.x][new_poz.y].tjulieta=v[aux.x][aux.y].tjulieta+1,c.push(new_poz);
        }
    }
    int tmin=1000000000;
    poz poz_tmin;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(v[i][j].tromeo==v[i][j].tjulieta and v[i][j].tromeo<tmin)tmin=v[i][j].tromeo,poz_tmin.x=i,poz_tmin.y=j;
    cout<<tmin+1<<' '<<poz_tmin.x<<' '<<poz_tmin.y;
    return 0;
}