Cod sursa(job #542196)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 25 februarie 2011 22:23:13
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include<stdio.h>
#include<memory>
#define nmax 100
#define nn 800000

typedef struct{
        int x;
        int y;
        }q;


int ro[nmax][nmax],jul[nmax][nmax],a[nmax][nmax];
int romx,romy,julx,july;

int x[]={-1, 0, 1,-1, 1,-1, 0, 1};
int y[]={-1,-1,-1, 0, 0, 1, 1, 1};

int n,m;

void rezolvare(int x1,int y1,int aux[nmax][nmax]){
     
q gelu[nmax*nmax];    

memset(aux, -1, sizeof(int) * nmax * nmax);  
  
  int i,j;
    
  int inc=0,sf=1;
  int sum=1;    
  int el1,el2,el3,el4;
  
  gelu[1].x=x1;
  gelu[1].y=y1;
  aux[x1][y1]=1;
 
  while( inc <= sf ) 
  {   ++inc;  
       el1=gelu[inc].x;
       el2=gelu[inc].y;
       sum=aux[el1][el2];

     for(i=0; i<8; ++i){ 
      el3=el1+x[i]; 
      el4=el2+y[i];
 
    
      if( el3 > 0 && el3 <= n && el4 > 0 && el4 <=m && a[el3][el4] != -1 && aux[el3][el4] == -1){
      aux[el3][el4]=1+sum;
      
      ++sf;
      gelu[sf].x=el3;
      gelu[sf].y=el4;
      }
      } 
  } 
}
      
int main()
{
    
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
    
int i,j;    
char ch,str[106];    

scanf("%d%d\n",&n,&m);

     for(i=1;i<=n;i++)  
     {  
         fgets(str,105,stdin);  
           
         for(j=1;j<=m;j++){  
             ch=str[j-1];  
             if( ch == 'X')
             a[i][j]=-1;
             else 
                  if(ch == 'R'){  
                               romx=i;  
                               romy=j;  
                                } 
                                else 
                                if(ch == 'J'){  
                                 julx=i;  
                                 july=j;  
                                 }  
                           }  
     } 

  rezolvare(romx,romy,ro);
  rezolvare(julx,july,jul);  
     
int optimx=n+1,optimy=m+1,optimval=nn;
int aux1,aux2;

  for(i=1; i<=n; ++i)
   for(j=1; j<=m; ++j)
    if(a[i][j] != -1 && ro[i][j]!=-1 && jul[i][j]!=-1){
   aux1 = ro[i][j];
   aux2 = jul[i][j]; 
 
   if( aux1 == aux2 && aux1 < optimval){     
      optimx=i;   
      optimy=j; 
      optimval=aux1;
   } 
   }
    printf("%d %d %d\n",optimval,optimx,optimy);
    
    return 0;
}