Cod sursa(job #216053)

Utilizator MikeysMihai Tiganus Mikeys Data 22 octombrie 2008 12:05:17
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream.h>

struct Coada{ int c,l,d; }R[10000],J[10000],alfa,beta,y;

int dcol[4]={-1,0,1,0},dlin[4]={0,-1,0,1};

int cod(char lit)
{
  if(lit=='X') return -1;
  else if(lit=='R') return 1;
  else if(lit=='J') return 2;
}

int map[100][100],romeo[100][100],julieta[100][100];

int main()
{
  ifstream in("rj.in");
  ofstream out("rj.out");
  int n,m,i,j,inc=0,sf=-1,k,rlin,rcol,jlin,jcol,sfj=-1,incj=0,linmin=101,colmin=101,minimum=10001;
  char x;
  char tst[100];
  in >>n>>m;
  i=1;
  j=0;
  while(j<=n)
  {
    x=in.get();
    if(x=='R') rcol=i,rlin=j;
    else if(x=='J') jcol=i,jlin=j;
    if(x=='\n') j++,i=1;
    else if(x!=' ')
     map[j][i]=cod(x),i++;
    else if(x==' ') i++;
  }
  
  
  for(i=0;i<=n+1;i++)
    for(j=0;j<=m+1;j++)
      map[i][0]=-1,map[0][j]=-1,map[n+1][j]=-1,map[i][m+1]=-1;
  R[++sf].l=rlin;
  R[sf].c=rcol;
  R[sf].d=0;
  J[++sfj].l=jlin;
  J[sfj].c=jcol;
  J[sfj].d=0;
  while(sf-inc+1>0)
  {
    alfa=R[inc++];
    beta=J[incj++];
    for(k=0;k<4;k++)
    {
       //romeo
       y.l=alfa.l+dlin[k];
       y.c=alfa.c+dcol[k];
       if(map[y.l][y.c]==0 && romeo[y.l][y.c]==0)
       {
         y.d=alfa.d+1;
         romeo[y.l][y.c]=y.d;
         R[++sf]=y; 
       }
       
       //julieta
       y.l=beta.l+dlin[k];
       y.c=beta.c+dcol[k];
       if(map[y.l][y.c]==0 && julieta[y.l][y.c]==0)
       {
         y.d=beta.d+1;
         julieta[y.l][y.c]=y.d;
         J[++sfj]=y; 
       }
    }
  }  
  
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      if(romeo[i][j]!=0) if(romeo[i][j]==julieta[i][j]) if(romeo[i][j]<minimum) minimum=romeo[i][j],linmin=i,colmin=j;
  out <<linmin<<" "<<colmin<<" "<<minimum;

  in.close();
  out.close();
  return 0;
}