Cod sursa(job #1481894)

Utilizator dominiciorgandaDominic Iorganda dominiciorganda Data 5 septembrie 2015 15:29:17
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.61 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int f[120][120],r[120][120],j[120][120],k,i,m,x,xi,xu,mi,mu,xo,xc,mo,mc,ok,cmin,kmin,imin;
string g[120];
queue <int> rx,rm,jx,jm;
int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin>>x>>m;
    for(k=0;k<=x;k++)
        getline(fin,g[k]);
    for (k=1;k<=x;k++)
        for (i=1;i<=m;i++)
            r[k][i]=j[k][i]=x*m+2;
    for(k=1;k<=x;k++)
    {
        for(i=0;i<m;i++)
        {
            if(g[k][i]=='X')
                f[k][i+1]=1;
            if(g[k][i]=='R')
            {
                r[k][i+1]=1;
                xi=k;
                mi=i+1;
            }
            if(g[k][i]=='J')
            {
                j[k][i+1]=1;
                xo=k;
                mo=i+1;
            }
        }
    }

    for(k=1;k<=x;k++)
        f[k][0]=f[k][m+1]=1;
    for(k=1;k<=m;k++)
        f[0][k]=f[x+1][k]=1;
    rx.push(xi); rm.push(mi);
    jx.push(xo); jm.push(mo);
    for(cmin=m*x+2;!rx.empty();)
    {
        xc=rx.front(); rx.pop();
        mc=rm.front(); rm.pop();
        xu=xc-1; mu=mc-1;
        if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);
             }
         }
         xu=xc-1; mu=mc+1;
        if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);
             }
         }
         xu=xc+1; mu=mc+1;
          if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);
             }
         }
         xu=xc+1; mu=mc-1;
        if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);

             }
         }
        xu=xc+1; mu=mc;
        if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);
             }
         }
         xu=xc-1; mu=mc;
        if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);
             }
         }
         xu=xc; mu=mc+1;
          if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);
             }
         }
         xu=xc; mu=mc-1;
        if(f[xu][mu]==0)
         {
             if(r[xu][mu]>=r[xc][mc]+2)
             {
                 r[xu][mu]=r[xc][mc]+1;
                 rx.push(xu); rm.push(mu);

             }
         }

    }
    for(;!jx.empty();)
    {
        xc=jx.front(); jx.pop();
        mc=jm.front(); jm.pop();
        xu=xc+1; mu=mc;
        if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
         xu=xc-1; mu=mc;
        if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
         xu=xc; mu=mc+1;
          if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
         xu=xc; mu=mc-1;
        if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
         xu=xc-1; mu=mc+1;
        if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
         xu=xc-1; mu=mc-1;
        if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
         xu=xc+1; mu=mc+1;
          if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
         xu=xc+1; mu=mc-1;
        if(f[xu][mu]==0)
         {
             if(j[xu][mu]>=j[xc][mc]+2)
             {
                 j[xu][mu]=j[xc][mc]+1;
                 jx.push(xu); jm.push(mu);
             }
         }
    }
/*
    for(k=1;k<=x;k++)
    {
        for(i=1;i<=m;i++)
        {
            fout.width(4);
            fout<<r[k][i];
        }
        fout<<endl;
    }
    fout<<endl;fout<<endl;
    for(k=1;k<=x;k++)
    {
        for(i=1;i<=m;i++)
        {
            fout.width(4);
            fout<<j[k][i];
        }
        fout<<endl;
    }
*/
        for(k=1;k<=x;k++)
        {
            for(i=1;i<=m;i++)
            {
                if(r[k][i]==j[k][i]&&r[k][i]<cmin)
                {
                    cmin=r[k][i];
                    kmin=k;
                    imin=i;
                }
            }
        }

fout<<cmin<<" "<<kmin<<" "<<imin<<endl;
    return 0;
}