Cod sursa(job #1105872)

Utilizator Barcau_EmanuelBarcau Emanuel Barcau_Emanuel Data 12 februarie 2014 10:42:01
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int i,xr,yr,xj,yj,n,m,k,l,o,j,a[102][102],b[102][102];
char x;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

struct nod{
int x,y;
nod *urm;
}*vf,*sf;

void creare(nod *&vf,nod *&sf,int xx,int yy)
{
    if(vf==0)
    {
        vf=new(nod);
        vf->x=xx;
        vf->y=yy;
        vf->urm=0;
        sf=vf;
    }
    else
    {
        nod *c;
        c=new(nod);
        c->x=xx;
        c->y=yy;
        c->urm=0;
        sf->urm=c;
        sf=c;
    }
}

int ver(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m) return 1;
    return 0;
}

void leeR(int x,int y)
{
   int st,xx,yy,dr,i,j;

   st=dr;
   vf=sf=0;
   creare(vf,sf,x,y);

   st=dr;
   while(st<=dr)
   {
       x=vf->x;
       y=vf->y;
       for(i=0;i<8;i++)
       {
           xx=x+dx[i];
           yy=y+dy[i];
           if(ver(xx,yy)==1)
             {
                 if(a[xx][yy]==0||a[xx][yy]>a[x][y]+1)
                 {
                     a[xx][yy]=a[x][y]+1;
                     creare(vf,sf,xx,yy);
                     dr++;
                 }
             }
       }
       st++;
       nod *c;
       c=vf;
       vf=vf->urm;
       delete c;
   }

}

void leeJ(int x,int y)
{
   int st,xx,yy,dr,i,j;

   st=dr;
   vf=sf=0;
   creare(vf,sf,x,y);

   st=dr;
   while(st<=dr)
   {
       x=vf->x;
       y=vf->y;
       for(i=0;i<8;i++)
       {
           xx=x+dx[i];
           yy=y+dy[i];
           if(ver(xx,yy)==1)
             {
                 if(b[xx][yy]==0||b[xx][yy]>b[x][y]+1)
                 {
                     b[xx][yy]=b[x][y]+1;
                     creare(vf,sf,xx,yy);
                     dr++;
                 }
             }
       }
       st++;
       nod *c;
       c=vf;
       vf=vf->urm;
       delete c;
   }

}

int min(int x,int y)
{
    if(x<=0) return y;
    else if(x<y) return x;
    else return y;
}

void comp()
{
    int min1=99999;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     if(a[i][j]==b[i][j])
     {
         if(a[i][j]!=-1&&a[i][j]!=0)
         {
             if(a[i][j]<min1) min1=a[i][j],xr=i,yr=j;
         }
     }

    g<<min1<<" "<<xr<<" "<<yr;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f.get(x);
        for(j=1;j<=m;j++)
        {
            f.get(x);
            if(x=='X') a[i][j]=b[i][j]=-1;
            else if(x==' ') a[i][j]=b[i][j]=0;
            else if(x=='R') a[i][j]=1,xr=i,yr=j;
            else b[i][j]=1,xj=i,yj=j;
        }
    }

    leeR(xr,yr);
    leeJ(xj,yj);
    comp();

    return 0;
}