Cod sursa(job #1677437)

Utilizator SoniaFlorinaHorchidan Sonia-Florina SoniaFlorina Data 6 aprilie 2016 16:12:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

char mm[101][101];
int R[101][101],J[101][101];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int xR, yR, xJ, yJ, tmin=10000, a, b;

struct Element
{
    int l,c,d;
};

Element x,y;
queue <Element> Q;

void Romeo(int x0, int y0)
{
    x.l=xR;
    x.c=yR;
    R[x0][y0]=0;
    Q.push(x);
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for(int k=0;k<4;k++)
        {
            y.l=x.l+dx[k];
            y.c=x.c+dy[k];
            if(R[y.l][y.c]==-2)
            {
                y.d=x.d+1;
                R[y.l][y.c]=y.d;
                Q.push(y);
            }
        }
    }

    /*for(int i=1; i<=n; i++)
    {
        for(int j=0; j<n; j++)
            cout<<R[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;*/
}

void Julieta(int x0, int y0)
{
    while(!Q.empty())
        Q.pop();
    x.l=x.c=x.d=0;
    y.l=y.c=y.d=0;
    x.l=xJ;
    x.c=yJ;
    J[x0][y0]=0;
    Q.push(x);
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for(int k=0;k<4;k++)
        {
            y.l=x.l+dx[k];
            y.c=x.c+dy[k];
            if(J[y.l][y.c]==-2)
            {
                y.d=x.d+1;
                J[y.l][y.c]=y.d;
                Q.push(y);
            }
        }
    }
    /*for(int i=1; i<=n; i++)
    {
        for(int j=0; j<n; j++)
            cout<<J[i][j]<<' ';
        cout<<endl;
        }*/
}



int main()
{

    in>>n>>m;
    int i,j;
    for(i=0;i<=n;i++)
        in.getline(mm[i],100);
    for(i=0;i<=n;i++)
        for(j=0;j<m;j++)

            if(mm[i][j]=='X')
            {
                J[i][j]=-1;
                R[i][j]=-1;
            }
            else
            {
                if(mm[i][j]=='R')
                {
                    xR=i;
                    yR=j;
                    J[i][j]=-2;
                    R[i][j]=0;
                }
                else
                    if(mm[i][j]=='J')
                    {
                        xJ=i;
                        yJ=j;
                        J[i][j]=0;
                        R[i][j]=-2;
                    }
                    else
                        if(mm[i][j]==' ')
                        {
                            R[i][j]=-2;
                            J[i][j]=-2;
                        }
            }



    Romeo(xR, yR);
    Julieta(xJ,yJ);

    for(i=1;i<=n;i++)
        for(j=0;j<m;j++)
            if (R[i][j]==J[i][j] && R[i][j]!=-1 && R[i][j]!=-2 && R[i][j]!=0)
                if(R[i][j]<tmin)
                {
                    tmin=R[i][j];
                    a=i;
                    b=j+1;
                }
    out<<tmin<<' '<<a<<' '<<b;



    return 0;
}