Cod sursa(job #1825639)

Utilizator SirbuSirbu Ioan Sirbu Data 9 decembrie 2016 15:35:49
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");

queue < pair < int, int > > r;
queue < pair < int, int > > ju;

int di[8]={1,-1,0,0,-1,-1,1,1};
int dj[8]={0,0,1,-1,-1,1,-1,1};
int romeo[101][101];
int julieta[101][101];

string costel;


int n,m,startxr,startyr,finalxr,finalyr;
int startxj,startyj,finalxj,finalyj;

bool okr (int i, int j)
{
    if (i<1 || i>n || j<1 || j>m || romeo[i][j]==-1) return 0;
    return 1;
}
bool okj (int i, int j)
{
    if (i<1 || i>n || j<1 || j>m || julieta[i][j]==-1) return 0;
    return 1;
}

void leeromeo()
{
    int i,j,vecini,vecinj;
    romeo[startxr][startyr]=1;
    r.push(make_pair(startxr,startyr));
    while (!r.empty())
    {
        i=r.front().first;
        j=r.front().second;
        r.pop();
        for (int k=0;k<8;k++)
        {
            vecini=i+di[k];
            vecinj=j+dj[k];
            if (okr(vecini,vecinj) && romeo[vecini][vecinj]<1)
            {
                r.push(make_pair(vecini,vecinj));
               romeo[vecini][vecinj]=romeo[i][j]+1;
            }
        }
    }
}

void leejulieta()
{
    int i,j,vecini,vecinj;
    julieta[startxj][startyj]=1;
    ju.push(make_pair(startxj,startyj));
    while (!ju.empty())
    {
        i=ju.front().first;
        j=ju.front().second;
        ju.pop();
        for (int k=0;k<8;k++)
        {
            vecini=i+di[k];
            vecinj=j+dj[k];
            if (okj(vecini,vecinj) && julieta[vecini][vecinj]<1)
            {
               ju.push(make_pair(vecini,vecinj));
               julieta[vecini][vecinj]=julieta[i][j]+1;
            }
        }
    }
}


int main ()
{
    char x;
    fin >> n >> m;
    getline(fin,costel,'\n');
    for (int i=1;i<=n;i++)
        {
            getline(fin,costel,'\n');
            for (int j=0;j<costel.size();j++)
                if (costel[j]=='X') {romeo[i][j+1]=-1; julieta[i][j+1]=-1;}
                else if (costel[j]=='R') {startxr=i;startyr=j+1;}
                else if (costel[j]=='J') {startxj=i;startyj=j+1;}
        }
    leejulieta();
    leeromeo();
    int finalx=0,finaly=0;
    int tmin=10005;
    for (int linie=1;linie<=n;linie++)
        for (int col=1;col<=m;col++)
        {
            if (romeo[linie][col]==julieta[linie][col] && romeo[linie][col]<tmin && romeo[linie][col]!=-1)
            {
                tmin=romeo[linie][col];
                finalx=linie;
                finaly=col;
            }
        }
    fout << finalx << " " << finaly << " " << tmin << "\n";

}