Cod sursa(job #377913)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 26 decembrie 2009 21:03:53
Problema Rj Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <stdio.h>

char tabla[102][102];
//int v1[10000],v2[10000];//vizitat
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};
int viz1[101][101],viz2[101][101];
struct poz{
  int generatia,x,y;
}coada1[10000],coada2[10000];

int lee(){
   int lir,lsr,lij,lsj,i,j,limi1=0,limi2=0,lims1=1,lims2=1,ok1,ok2;
   lir=lij=0;
   lsr=lsj=1;
   //adaug in coada poz curenta
     //pt romeo
     coada1[lir].x=xr;
     coada1[lir].y=yr;
     coada1[lir].generatia=0;
     //pt julieta
     coada2[lij].x=xj;
     coada2[lij].y=yj;
     coada2[lij].generatia=0;
     //adaug in coada toti vecinii lor
     while(lsr>lir && lsj>lij){
        //adauga toti vec patr in care e romeo
        for(i=0;i<8;i++)
           if(tabla[coada1[lir].x+dirx[i]][coada1[lir].y+diry[i]]!='X'){
              if(viz1[coada1[lir].x+dirx[i]][coada1[lir].y+diry[i]]==0){
                coada1[lsr].x=coada1[lir].x+dirx[i];
                coada1[lsr].y=coada1[lir].y+diry[i];
                coada1[lsr].generatia=coada1[lir].generatia+1;
                viz1[coada1[lir].x+dirx[i]][coada1[lir].y+diry[i]]=1;
                lsr++;
              }
           }
       lir++;
       //adauga toti vec patr in care e julieta
        for(i=0;i<8;i++)
           if(tabla[coada2[lij].x+dirx[i]][coada2[lij].y+diry[i]]!='X'){
              if(viz2[coada2[lij].x+dirx[i]][coada2[lij].y+diry[i]]==0){
                coada2[lsj].x=coada2[lij].x+dirx[i];
                coada2[lsj].y=coada2[lij].y+diry[i];
                coada2[lsj].generatia=coada2[lij].generatia+1;
                viz2[coada2[lij].x+dirx[i]][coada2[lij].y+diry[i]]=1;
                lsj++;
              }
           }
        lij++;      

    ok1=0,ok2=0;
     //daca s-a term gen romeo
     if(lir==lims1){
         limi1=lir;
         lims1=lsr;
         ok1=1;
     }
     //daca s-a term gen julieta
     if(lij==lims2){
         limi2=lij;
         lims2=lsj;
         ok2=1;
     }
 
     //caut elem comune intre cele doua generatii
     if(ok1&&ok2)
     for(i=limi1;i<lims1;i++)
        for(j=limi2;j<lims2;j++)
           if((coada1[i].x==coada2[j].x)&&(coada1[i].y==coada2[j].y)){
             xint=coada2[j].x;
             yint=coada2[j].y;
             return coada2[j].generatia;
           }


     //caut elem comune intre cele doua generatii
  /*   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;
             return coada2[j].generatia;
           }

*/
     
     }
}

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]='X';
   for(i=0;i<m+1;i++)tabla[0][i]='X';
   for(i=0;i<m+1;i++)tabla[n+1][i]='X';
   for(i=0;i<n+1;i++)tabla[m+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;
       }
     }
   fscanf(fin,"%c",&q);
   }
//afisarea de test...
   /*for(i=1;i<=n;i++){
     for(j=1;j<=m;j++)
       printf("%c",tabla[i][j]);
   printf("\n");
   }*/
   FILE *fout=fopen("rj.out","w");
   fprintf(fout,"%d %d %d\n",lee(),xint,yint);
   
return 0;   
}