Cod sursa(job #216207)

Utilizator MikeysMihai Tiganus Mikeys Data 23 octombrie 2008 13:00:33
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream.h>
#include <iomanip.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.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.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;
          }
          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;
}