Cod sursa(job #216372)

Utilizator MikeysMihai Tiganus Mikeys Data 24 octombrie 2008 09:47:42
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <fstream.h>   
  
struct Coada{ int c,l,d; }c[10000],alfa,y;  
  
int dcol[8]={-1,0,1,0,-1,1,-1,1},dlin[8]={0,-1,0,1,-1,-1,1,1};  
  
int cod(char lit)  
{  
  if(lit=='X') return -1;  
  else if(lit=='R') return 1;  
  else if(lit=='J') return 2;  
  return 0;  
}  
  
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,linmin=0,colmin=0,minimum=-1;  
  char x;  
  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' || i>m) 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;  
  c[++sf].l=rlin;  
  c[sf].c=rcol;  
  c[sf].d=1;  
  while(sf-inc+1>0)  
  {  
    alfa=c[inc++];  
    for(k=0;k<8;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 || romeo[y.l][y.c]>alfa.d+1) && y.l<=n && y.c<=m && y.c>0 && y.l>0)  
       {  
         y.d=alfa.d+1;  
         romeo[y.l][y.c]=y.d;  
         c[++sf]=y;   
       }  
    }  
  }   
  sf=-1;  
  inc=0;   
  c[++sf].l=jlin;  
  c[sf].c=jcol;  
  c[sf].d=1;  
  while(sf-inc+1>0)  
  {  
    alfa=c[inc++];  
    for(k=0;k<8;k++)  
    {  
       //julieta  
       y.l=alfa.l+dlin[k];  
       y.c=alfa.c+dcol[k];  
       if(map[y.l][y.c]==0 && (julieta[y.l][y.c]==0 || julieta[y.l][y.c]>alfa.d+1) && y.l<=n && y.c<=m && y.c>0 && y.l>0)  
       {  
         y.d=alfa.d+1;  
         julieta[y.l][y.c]=y.d;  
         c[++sf]=y;   
       }  
    }  
  }   
  
/* 
  for(i=0;i<=n+1;i++) 
  { 
    for(j=0;j<=m+1;j++) 
      out <<setw(3)<<map[i][j]<<" "; 
    out <<"\n"; 
  }    
  out <<"\n"; 
  for(i=0;i<=n+1;i++) 
  { 
    for(j=0;j<=m+1;j++) 
      out <<setw(3)<<romeo[i][j]<<" "; 
    out <<"\n"; 
  } 
  out <<"\n"; 
  for(i=0;i<=n+1;i++) 
  { 
    for(j=0;j<=m+1;j++) 
      out <<setw(3)<<julieta[i][j]<<" "; 
    out <<"\n"; 
  } out <<"\n";     
  */  
  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==-1)  
          {  
             minimum=romeo[i][j],linmin=i,colmin=j;  
             i=0;  
             j=0;  
          }  
          /*else if(romeo[i][j]==minimum) 
          { 
          if(linmin>i) 
            minimum=romeo[i][j],linmin=i,colmin=j; 
          if(linmin==i && colmin>j) 
            minimum=romeo[i][j],linmin=i,colmin=j; 
          }*/  
        }  
          
  out <<minimum<<" "<<linmin<<" "<<colmin;  
  
  in.close();  
  out.close();  
  return 0;  
}