Cod sursa(job #323116)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 10 iunie 2009 19:43:50
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.5 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a,b) (a>b)?a:b
struct pct{long x,y;}sr[10050],sj[10050],poz;
long n,i,j,a[105][105],aa[105][105],xr,yr,xj,yj,p,u1,u2,m,f;
char c;
void dooo(pct sr[],long a[][105],long aa[][105],long p,long &u1,long dx,long dy)
{if(a[sr[p].x+dx][sr[p].y+dy]==0)
   {sr[++u1]=sr[p];
    sr[u1].x+=dx;
    sr[u1].y+=dy;
    a[sr[u1].x][sr[u1].y]=a[sr[p].x][sr[p].y]+1;
    if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y]&&(a[sr[u1].x][sr[u1].y]<=a[poz.x][poz.y]||(!poz.x&&!poz.y)))
      if((poz.x>sr[u1].x||(poz.x==sr[u1].x&&poz.y>sr[u1].y))||(!poz.x&&!poz.y))
        {poz=sr[u1];
        f=a[poz.x][poz.y];}}}
int main()
{
 freopen("rj.in","r",stdin);
 freopen("rj.out","w",stdout);
 scanf("%ld%ld\n",&n,&m);
 for(i=1;i<=n;++i)
    {c='x';
     for(j=1;c!='\n'&&j<=m+1;++j)
        {scanf("%c",&c);
         if(c=='X')a[i][j]=-1;
         else if(c=='R'){a[i][j]=1;xr=i,yr=j;}
               else if(c=='J'){a[i][j]=1;xj=i,yj=j;}}}
 for(i=0;i<=n+1;++i)
    a[i][0]=a[i][m+1]=-1;
 for(i=0;i<=m+1;++i)
    a[0][i]=a[n+1][i]=-1;
 memcpy(aa,a,sizeof(a));
 sr[1].x=xr;
 sr[1].y=yr;
 sj[1].x=xj;
 sj[1].y=yj;
 p=1;
 u1=1;
 u2=1;
 while(p<=u1||p<=u2)
  {if(p<=u1)
     {dooo(sr,a,aa,p,u1,0,1);
      dooo(sr,a,aa,p,u1,1,0);
      dooo(sr,a,aa,p,u1,0,-1);
      dooo(sr,a,aa,p,u1,-1,0);
      dooo(sr,a,aa,p,u1,1,1);
      dooo(sr,a,aa,p,u1,-1,1);
      dooo(sr,a,aa,p,u1,1,-1);
      dooo(sr,a,aa,p,u1,-1,-1);}
   if(p<=u2)
     {dooo(sj,aa,a,p,u2,0,1);
      dooo(sj,aa,a,p,u2,1,0);
      dooo(sj,aa,a,p,u2,0,-1);
      dooo(sj,aa,a,p,u2,-1,0);
      dooo(sj,aa,a,p,u2,1,1);
      dooo(sj,aa,a,p,u2,-1,1);
      dooo(sj,aa,a,p,u2,1,-1);
      dooo(sj,aa,a,p,u2,-1,-1);}
  /*if(p<=u1)
  if((f&&a[sr[p].x][sr[p].y]<f)||!f)
  {if(a[sr[p].x+1][sr[p].y]==0)
     {sr[++u1]=sr[p];
      ++sr[u1].x;
      a[sr[u1].x][sr[u1].y]=a[sr[p].x][sr[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sr[u1].x||(poz.x==sr[u1].x&&poz.y>sr[u1].y))poz=sr[u1];f=max(a[sr[u1].x][sr[u1].y],aa[sr[u1].x][sr[u1].y]);}}
   if(a[sr[p].x-1][sr[p].y]==0)
     {sr[++u1]=sr[p];
      --sr[u1].x;
      a[sr[u1].x][sr[u1].y]=a[sr[p].x][sr[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sr[u1].x||(poz.x==sr[u1].x&&poz.y>sr[u1].y))poz=sr[u1];f=max(a[sr[u1].x][sr[u1].y],aa[sr[u1].x][sr[u1].y]);}}
   if(a[sr[p].x][sr[p].y+1]==0)
     {sr[++u1]=sr[p];
      ++sr[u1].y;
      a[sr[u1].x][sr[u1].y]=a[sr[p].x][sr[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sr[u1].x||(poz.x==sr[u1].x&&poz.y>sr[u1].y))poz=sr[u1];f=max(a[sr[u1].x][sr[u1].y],aa[sr[u1].x][sr[u1].y]);}}
   if(a[sr[p].x][sr[p].y-1]==0)
     {sr[++u1]=sr[p];
      --sr[u1].y;
      a[sr[u1].x][sr[u1].y]=a[sr[p].x][sr[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sr[u1].x||(poz.x==sr[u1].x&&poz.y>sr[u1].y))poz=sr[u1];f=max(a[sr[u1].x][sr[u1].y],aa[sr[u1].x][sr[u1].y]);}}}
//////////////////////////////////////////////////////////////////////////////
  if(p<=u2)
  if((f&&aa[sj[p].x][sj[p].y]<f)||!f)
  {if(aa[sj[p].x+1][sj[p].y]==0)
     {sj[++u2]=sj[p];
      ++sj[u2].x;
      aa[sj[u2].x][sj[u2].y]=aa[sj[p].x][sj[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sj[u2].x||(poz.x==sj[u2].x&&poz.y>sj[u2].y))poz=sj[u2];f=max(a[sj[u2].x][sj[u2].y],aa[sj[u2].x][sj[u2].y]);}}
   if(aa[sj[p].x-1][sj[p].y]==0)
     {sj[++u2]=sj[p];
      --sj[u2].x;
      aa[sj[u2].x][sj[u2].y]=aa[sj[p].x][sj[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sj[u2].x||(poz.x==sj[u2].x&&poz.y>sj[u2].y))poz=sj[u2];f=max(a[sj[u2].x][sj[u2].y],aa[sj[u2].x][sj[u2].y]);}}
   if(aa[sj[p].x][sj[p].y+1]==0)
     {sj[++u2]=sj[p];
      ++sj[u2].y;
      aa[sj[u2].x][sj[u2].y]=aa[sj[p].x][sj[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sj[u2].x||(poz.x==sj[u2].x&&poz.y>sj[u2].y))poz=sj[u2];f=max(a[sj[u2].x][sj[u2].y],aa[sj[u2].x][sj[u2].y]);}}
   if(aa[sj[p].x][sj[p].y-1]==0)
     {sj[++u2]=sj[p];
      --sj[u2].y;
      aa[sj[u2].x][sj[u2].y]=aa[sj[p].x][sj[p].y]+1;
      if(a[sr[u1].x][sr[u1].y]==aa[sr[u1].x][sr[u1].y])
      {if(poz.x>sj[u2].x||(poz.x==sj[u2].x&&poz.y>sj[u2].y))poz=sj[u2];f=max(a[sj[u2].x][sj[u2].y],aa[sj[u2].x][sj[u2].y]);}}}
*/////////////////////////////////////////////////////////////////////////////
   ++p;}
 printf("%ld %ld %ld\n",f,poz.x,poz.y);
 return 0;
}