Cod sursa(job #378071)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 27 decembrie 2009 14:03:17
Problema Rj Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.6 kb
#include <stdio.h>

char tabla[105][105];
int xr,yr,xj,yj,xint,yint;
const int dirx[8]={-1,-1,0,1,1,1,0,-1},diry[8]={0,1,1,1,0,-1,1,-1};
struct poz{
  char x,y;
}coada1[10010],coada2[10010];


void cauta_minim(int a,int b,int c, int d){
    int x=32000,y=32000;
    int i,j;
    for(i=a;i<b;i++)
      for(j=c;j<d;j++)
       if((coada1[i].x==coada2[j].x)&&(coada1[i].y==coada2[j].y)){
            if(x>coada1[i].x){
               x=coada1[i].x;
               y=coada1[i].y;
            }
            if((x==coada1[i].x)&&(y>coada1[i].y)){
               x=coada1[i].x;
               y=coada1[i].y;             
            }
       }
   xint=x;
   yint=y;
}

int lee(){
   int lir,lsr,lij,lsj,i,j,u,v,gr=1,gj=1;
   lir=lij=0;
   lsr=lsj=1;
   //adaug in coada poz curenta
     //pt romeo
     coada1[lir].x=xr;
     coada1[lir].y=yr;
     tabla[xr][yr]=2;
     //coada1[lir].generatia=1;
     //pt julieta
     coada2[lij].x=xj;
     coada2[lij].y=yj;
     tabla[xj][yj]=3;
     //coada2[lij].generatia=1;
     //adaug in coada toti vecinii lor
     while(lsr>lir && lsj>lij){
        //adauga toti vec patr in care e romeo(adica o noua intreaga genereatie)
        j=lsr;
        while(lir<j){
        for(i=0;i<8;i++){
           u=coada1[lir].x+dirx[i];
           v=coada1[lir].y+diry[i];
           if(tabla[u][v]!='X'){
              if(tabla[u][v]%2){
                coada1[lsr].x=u;
                coada1[lsr].y=v;
                //coada1[lsr].generatia=coada1[lir].generatia+1;
                tabla[u][v]*=2;
                lsr++;
              }
           }
        }
       lir++;
       }
       gr++;
       //adauga toti vec patr in care e julieta
        j=lsj;
        while(lij<j){
        for(i=0;i<8;i++){
           u=coada2[lij].x+dirx[i];
           v=coada2[lij].y+diry[i];
           if(tabla[u][v]!='X'){
              if(tabla[u][v]%3){
                coada2[lsj].x=u;
                coada2[lsj].y=v;
                //coada2[lsj].generatia=coada2[lij].generatia+1;
                tabla[u][v]*=3;
                lsj++;
              }
           }
        }
        lij++;      
       }
       gj++;
   /*  printf("asa arata generatia curenta:\n");  
     printf("romeo:\n");
     for(i=lir;i<lsr;i++)printf("(%d %d) ",coada1[i].x,coada1[i].y);
     printf("\njulieta:\n");
     for(i=lij;i<lsj;i++)printf("(%d %d) ",coada2[i].x,coada2[i].y);
     */
     for(i=lir;i<lsr;i++)
        for(j=lij;j<lsj;j++)
           if((coada1[i].x==coada2[j].x)&&(coada1[i].y==coada2[j].y)){
             //xint=coada2[j].x;
             //yint=coada2[j].y;
             cauta_minim(lir,lsr,lij,lsj);
             return gr;//coada2[j].generatia;
           }

    // printf("\n");
     
     }
     return -1;
}

int main(){
   int n,m;
   int i,j;
   char q;
   FILE *fin=fopen("rj.in","r");
   fscanf(fin,"%d %d\n",&n,&m);
   //init marginile matr cu x
   for(i=0;i<=n+1;i++)tabla[i][0]=tabla[i][m+1]='X';
   for(i=0;i<=m+1;i++)tabla[0][i]=tabla[n+1][i]='X';
   
   
   for(i=1;i<=n;i++){
     for(j=1;j<=m;j++){
       fscanf(fin,"%c",&tabla[i][j]);
       if(tabla[i][j]=='R'){
         xr=i;
         yr=j;
       }
       if(tabla[i][j]=='J'){
         xj=i;
         yj=j;
       }
       if(tabla[i][j]==' ')tabla[i][j]=1;
     }
   fscanf(fin,"%c",&q);
   }
 /*  
   for(i=0;i<=n+1;i++){
     for(j=0;j<=m+1;j++)
       printf("%c",tabla[i][j]);
     printf("\n");
   }
   */
   fclose(fin);

   FILE *fout=fopen("rj.out","w");
   fprintf(fout,"%d %d %d\n",lee(),xint,yint);
   fclose(fout);
return 0;   
}