Cod sursa(job #1372978)

Utilizator madalin98Gherghe Madalin madalin98 Data 4 martie 2015 16:06:08
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.01 kb
#include<iostream>/*romeo si julieta*/
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int M[110][110],N[110][110];
int main()
{
    int x,y,xx,yy,n,i,j,m,rx,ry,jx,jy,dm=32000,xm,ym;
    char b[110];
    f>>n>>m;f.get();
    for (i=1;i<=n;i++)
        {
            f.get(b,110);
            f.get();
            for (j=1;j<=m;j++)
                if (b[j-1]=='X'){M[i][j]=0;N[i][j]=0;}
                else
                    if (b[j-1]=='R') {rx=i;ry=j;M[i][j]=1;N[i][j]=-1;}
                    else
                        if (b[j-1]=='J') {jx=i;jy=j;M[i][j]=-1;N[i][j]=1;}
                            else {M[i][j]=-1;N[i][j]=-1;}
        }
    x=rx;y=ry;
    queue<int>qx;
    queue<int>qy;
    qx.push(x);
    qy.push(y);
    while(qx.empty()!=true)
    {
        xx=qx.front();
        yy=qy.front();
        if(M[xx-1][yy]==-1||M[xx-1][yy]>M[xx][yy]+1)
        {
            M[xx-1][yy]=M[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy);
        }
        if(M[xx][yy+1]==-1||M[xx][yy+1]>M[xx][yy]+1)
        {
            M[xx][yy+1]=M[xx][yy]+1;
            qx.push(xx);
            qy.push(yy+1);
        }
        if(M[xx+1][yy]==-1||M[xx+1][yy]>M[xx][yy]+1)
        {
            M[xx+1][yy]=M[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy);
        }
         if(M[xx][yy-1]==-1||M[xx][yy-1]>M[xx][yy]+1)
        {
            M[xx][yy-1]=M[xx][yy]+1;
            qx.push(xx);
            qy.push(yy-1);
        }
         if(M[xx-1][yy-1]==-1||M[xx-1][yy]>M[xx][yy]+1)
        {
            M[xx-1][yy-1]=M[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy-1);
        }
         if(M[xx-1][yy+1]==-1||M[xx-1][yy]>M[xx][yy]+1)
        {
            M[xx-1][yy+1]=M[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy+1);
        }
         if(M[xx+1][yy+1]==-1||M[xx-1][yy]>M[xx][yy]+1)
        {
            M[xx+1][yy+1]=M[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy+1);
        }
         if(M[xx+1][yy-1]==-1||M[xx-1][yy]>M[xx][yy]+1)
        {
            M[xx+1][yy-1]=M[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy-1);
        }
        qx.pop();
        qy.pop();
    }
    x=jx;y=jy;
    qx.push(x);
    qy.push(y);
    while(qx.empty()!=true)
    {
        xx=qx.front();
        yy=qy.front();
        if(N[xx-1][yy]==-1||N[xx-1][yy]>N[xx][yy]+1)
        {
            N[xx-1][yy]=N[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy);
        }
        if(N[xx][yy+1]==-1||N[xx][yy+1]>N[xx][yy]+1)
        {
            N[xx][yy+1]=N[xx][yy]+1;
            qx.push(xx);
            qy.push(yy+1);
        }
        if(N[xx+1][yy]==-1||N[xx+1][yy]>N[xx][yy]+1)
        {
            N[xx+1][yy]=N[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy);
        }
         if(N[xx][yy-1]==-1||N[xx][yy-1]>N[xx][yy]+1)
        {
            N[xx][yy-1]=N[xx][yy]+1;
            qx.push(xx);
            qy.push(yy-1);
        }
         if(N[xx-1][yy-1]==-1||N[xx-1][yy]>N[xx][yy]+1)
        {
            N[xx-1][yy-1]=N[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy-1);
        }
         if(N[xx-1][yy+1]==-1||N[xx-1][yy]>N[xx][yy]+1)
        {
            N[xx-1][yy+1]=N[xx][yy]+1;
            qx.push(xx-1);
            qy.push(yy+1);
        }
         if(M[xx+1][yy+1]==-1||M[xx-1][yy]>M[xx][yy]+1)
        {
            M[xx+1][yy+1]=M[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy+1);
        }
         if(N[xx+1][yy-1]==-1||N[xx-1][yy]>N[xx][yy]+1)
        {
            N[xx+1][yy-1]=N[xx][yy]+1;
            qx.push(xx+1);
            qy.push(yy-1);
        }
        qx.pop();
        qy.pop();
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(M[i][j]==N[i][j]&&M[i][j]>0&&M[i][j]<dm){dm=M[i][j];
                                                         xm=i;ym=j;}
    g<<dm<<" "<<xm<<" "<<ym;
    return 0;
}