Cod sursa(job #383245)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 16 ianuarie 2010 10:02:41
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 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()
{
 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+1; i++) rr[i][0]=-1, rr[i][m+1]=-1, jj[i][0]=-1, jj[i][m+1]=-1;
 for(i=0; i<=m+1; i++) rr[0][i]=-1, rr[n+1][i]=-1, jj[0][i]=-1, jj[n+1][i]=-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);

 //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]!=-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
 {
  int coord,minx=30000,miny=30000;
  for(i=1; i<=t; i++)
  {
   if(sol[i].x<minx) minx=sol[i].x, miny=sol[i].y, coord=i;
   else if(sol[i].x==minx && sol[i].y<miny) miny=sol[i].y, coord=i;
   g<<sol[coord].val<<" "<<sol[coord].x<<" "<<sol[coord].y;
  }
 }
 f.close();
 g.close();

 return 0;
}