Cod sursa(job #382419)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 13 ianuarie 2010 17:50:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include<fstream.h>
#include<string.h>

#define N 500
#define X 101

ifstream f("rj.in");
ofstream g("rj.out");

struct punct { int x,y; } cd[N];

struct sl { int x,y,val; } sol[50];

int p,nrelem,rr[X][X],jj[X][X];

int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,1,0,-1};

void init()
{
 p=nrelem=0;
}

int vplin()
{
 if(nrelem==N) return 1;
 return 0;
}

int vgol()
{
 if(nrelem==0) return 1;
 return 0;
}

int add(punct x)
{
 if(vplin()==1) return 0;
 cd[(p+nrelem)%N]=x;
 nrelem++;
 return 1;
}

int extract(punct &x)
{
 if(vgol()==1) return 0;
 x=cd[p];
 p=(p+1)%N;
 nrelem--;
 return 1;
}

void lee(int a[X][X], punct pi)
{
 punct c1,c2;
 int i;
 init();
 add(pi);
 while(vgol()==0)
 {
  extract(c1);
  for(i=0; i<8; i++)
  {
   c2.x=c1.x+dx[i];
   c2.y=c1.y+dy[i];
   if(a[c2.x][c2.y]==0)
   {
    add(c2);
    a[c2.x][c2.y]=a[c1.x][c1.y]+1;
   }
  }
 }
}

/*void afis(int a[X][X], int n, int m)
{
 int i,j;
 for(i=1; i<=n; i++)
 {
  for(j=1; j<=m; j++)
     g<<a[i][j]<<" ";
  g<<endl;
 }
 g<<endl;
}*/

int main()
{
 sl slfin,aux;
 punct rom,jul;
 int k,n,m,i,j,lin,t=0,min=30000;
 char s[100];

 f>>n>>m;
 f.getline(s,100);

 for(i=0; i<=n; i++) rr[i][0]=-1, rr[i][m+1]=-1, jj[i][0]=-1, jj[i][m+1]=-1;
 for(i=0; i<=m; i++) rr[0][i]=-1, rr[n+1][i]=-1, jj[0][i]=-1, jj[n+1][i]=-1;
 rr[n+1][m+1]=jj[n+1][m+1]=-1;

 for(i=1; i<=n; i++)
 {
  j=0;
  f.getline(s,100);
  for(k=0; k<strlen(s); k++)
  {
   switch(s[k])
   {
    case 'R':
     rom.x=i;
     rom.y=++j;
     jj[i][j]=1, rr[i][j]=1;
     break;
    case 'J':
     jul.x=i;
     jul.y=++j;
     jj[i][j]=1, rr[i][j]=1;
     break;
    case 'X':
     ++j;
     jj[i][j]=-1, rr[i][j]=-1;
     break;
    default:
     ++j;
     break;
   }
  }
 }

 //afis(rr,n,m);
 //afis(jj,n,m);

 lee(rr,rom);
 lee(jj,jul);

 rr[rom.x][rom.y]=rr[jul.x][jul.y]=jj[rom.x][rom.y]=jj[jul.x][jul.y]=-1;
 //afis(rr,n,m);
 //afis(jj,n,m);

 for(i=1; i<=n; i++)
 for(j=1; j<=m; j++)
  if(rr[i][j]!=-1 && rr[i][j]!=0)
   if(rr[i][j]==jj[i][j])
     if(rr[i][j]=<min)
     {
      ++t;
      sol[t].x=i;
      sol[t].y=j;
      sol[t].val=rr[i][j];
     }

 if(t==1) g<<sol[1].val<<" "<<sol[1].x<<" "<<sol[1].y;
 else
 {
  for(i=1; i<=t-1; i++)
  for(j=i+1; j<=t; j++)
    if(sol[i].x>sol[j].x)
    {
     aux=sol[i];
     sol[i]=sol[j];
     sol[j]=aux;
    }
  lin=sol[1].x; i=1; min=30000;
  while(sol[i].x==lin)
  {
   if(sol[i].y<min)
   {
    min=sol[i].y;
    slfin.x=lin;
    slfin.y=sol[i].y;
    slfin.val=sol[i].val;
   }
   i++;
  }
  g<<slfin.val<<" "<<slfin.x<<" "<<slfin.y;
 }

 f.close();
 g.close();

 return 0;
}