Cod sursa(job #1806919)

Utilizator LaurIleIle Laurentiu Daniel LaurIle Data 15 noiembrie 2016 20:33:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <queue>

using namespace std;
int  b[105][105],a[105][105],i,j,ln,cn,k,xs,xf,yf,ys,n,m,mini=10000,ln2,cn2;
char v[105];
ifstream f("rj.in");
ofstream g("rj.out");
queue < pair < int,int > >Q;
pair < int,int > aux;
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

void read()
{
   f>>n>>m;
   for(i=0;i<n;i++)
   {
       f.get();
       f.get(v,105);
       for(j=0;j<m;j++)
       {
           if(v[j]=='X')
           {
              b[i+1][j+1]=-1;
              a[i+1][j+1]=-1;
           }

           if(v[j]=='R')
           {
               xs=i+1;
               ys=j+1;
           }
           if(v[j]=='J')
           {
               xf=i+1;
               yf=j+1;
           }
       }
   } f.close();
}

void bord()
{
    for(i=0;i<=n+1;i++)
    {
        b[i][0]=-1;
        b[i][m+1]=-1;
        a[i][0]=-1;
        a[i][m+1]=-1;
    }
    for(i=0;i<=m+1;i++)
    {
        b[0][i]=-1;
        b[n+1][i]=-1;
        a[0][i]=-1;
        a[n+1][i]=-1;
    }
}

void lee_ro()
{
    Q.push(make_pair(xs,ys));
    b[xs][ys]=1;i=1;
    while(!Q.empty())
    {
        aux=Q.front();
        Q.pop();
        for(k=0;k<8;k++)
        {
            ln=aux.first+dx[k];
            cn=aux.second+dy[k];
            if(b[ln][cn]==0)
            {

                Q.push(make_pair(ln,cn));
                b[ ln ][ cn ]=b[ aux.first ][ aux.second ]+1;
            }
        }
    }
}

void lee_jul()
{
    Q.push(make_pair(xf,yf));
    a[xf][yf]=1;i=1;
    while(!Q.empty())
    {
        aux=Q.front();
        Q.pop();
        for(k=0;k<8;k++)
        {
            ln=aux.first+dx[k];
            cn=aux.second+dy[k];
            if(a[ln][cn]==0)
            {
                Q.push(make_pair(ln,cn));
                a[ln][cn]=a[aux.first][aux.second]+1;
            }
        }
    }
}

void caut()
{
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            if(a[i][j]==b[i][j] && (a[i][j]!=-1 && b[i][j]!=-1) &&(a[i][j]!=0 && b[i][j]!=0)  && a[i][j]<mini)
            {
                ln2=i;
                cn2=j;
                mini=a[i][j];
            }
    }
    g<<a[ln2][cn2]<<" "<<ln2<<" "<<cn2;
}

int main()
{
    read();
    bord();
    lee_ro();
    lee_jul();
    caut();
   return 0;
}