Cod sursa(job #2128193)

Utilizator SahMatCodrea Andrei SahMat Data 11 februarie 2018 15:30:13
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <queue>

using namespace std;
ifstream fi("rj.in");
ofstream fo("rj.out");

char Map[101];
int a[101][101],b[101][101];
int di[8]={0,-1,-1,-1,0,1,1,1},dj[8]={1,1,0,-1,-1,-1,0,1};
int n,m,i,j,x,y,rx,ry,jx,jy,k;
queue <pair<int,int> > q;

void Lee1()
{
    int i2,j2;
    q.push(make_pair(rx,ry));

    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(int d=0;d<=7;d++)
        {
            i2=di[d]+i;
            j2=dj[d]+j;

            if(i2>=1 and i2<=n and j2>=1 and j2<=m and a[i2][j2]==0)
            {
                a[i2][j2]=a[i][j]+1;
                if(i==rx and j==ry)
                    a[i2][j2]+=2;
                q.push(make_pair(i2,j2));
            }
        }
    }

}

void Lee2()
{
    int i2,j2;
    q.push(make_pair(jx,jy));

    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(int d=0;d<=7;d++)
        {
            i2=di[d]+i;
            j2=dj[d]+j;

            if(i2>=1 and i2<=n and j2>=1 and j2<=m and b[i2][j2]==0)
            {
                b[i2][j2]=b[i][j]+1;
                if(i==jx and j==jy)
                    b[i2][j2]+=2;
                q.push(make_pair(i2,j2));
            }
        }
    }

}

int main()
{
    fi>>n>>m;
    fi.getline(Map,101);
    for(i=1;i<=n;i++)
     {fi.getline(Map,101);
     for(j=0;j<m;j++)
     {
         if(Map[j]==' ')
         {
             a[i][j+1]=0;
             b[i][j+1]=0;
         }

        if(Map[j]=='R')
        {
            rx=i;
            ry=j+1;
            a[i][j+1]=-2;
        }
        if(Map[j]=='J')
        {
            jx=i;
            jy=j+1;
             a[i][j+1]=0;
             b[i][j+1]=-2;
        }
        if(Map[j]=='X')
            {
                a[i][j+1]=-1;
                b[i][j+1]=-1;

            }

    }
     }


    Lee1();
    Lee2();
        /*for(i=1;i<=n;i++)
        {for(j=1;j<=m;j++)
        fo<<a[i][j];
        fo<<endl;
        }*/
        int mi=101*101;
   for(i=1;i<=n;i++)
   for(j=1;j<=m;j++)
   if(a[i][j]==b[i][j] and a[i][j]<mi and a[i][j]>0)
   {
       mi=a[i][j];
       x=i;
       y=j;
   }
   fo<<mi+1<<" "<<x<<" "<<y;
    return 0;
}