Cod sursa(job #182734)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 21 aprilie 2008 11:41:21
Problema Rj Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 4.57 kb
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 110
#define MAX 20000
const int dx[]={0,1,0,-1,-1,-1,1,1};
const int dy[]={1,0,-1,0,-1,1,-1,1};
struct pozitie{
       int x,y;
};
struct pozitie romeo,julieta,r[MAX],j[MAX],best;
int a[N][N],b[N][N],n,m,nrmin=INT_MAX;
void bordare(int n,int m){
     int i;
     for (i=0;i<=n+1;++i){
         a[i][0]=-1;
         a[i][m+1]=-1;
         b[i][0]=-1;
         b[i][m+1]=-1;
     }
     for (i=0;i<=m+1;++i){
         a[0][i]=-1;
         a[n+1][i]=-1;
         b[0][i]=-1;
         b[n+1][i]=-1;
     }
}
void scan(){
     int i,j;
     char c;
     freopen("rj.in","r",stdin);
     freopen("rj.out","w",stdout);
     scanf("%d%d\n",&n,&m);
     bordare(n,m);
     for (i=1;i<=n;++i){
         for (j=1;j<=m+1;++j){
             scanf("%c",&c);
             if (c=='R'){
                romeo.x=i;
                romeo.y=j;
                a[i][j]=1;
                b[i][j]=0;
             }
             if (c=='J'){
                julieta.x=i;
                julieta.y=j;
                a[i][j]=0;
                b[i][j]=1;
             }
             if (c=='X'){
                a[i][j]=-1;
                b[i][j]=-1;
             }
             if (c==' '){
                a[i][j]=0;
                b[i][j]=0;
             }
         }
         //scanf("\n");
     }
}
int compara(const void *a,const void *b){
    struct pozitie *aa=(struct pozitie*)a,*bb=(struct pozitie*)b;
    if (aa->x>bb->x)
       return 1;
    if (aa->x<bb->x)
       return -1;
    if (aa->y>bb->y)
       return 1;
    if (aa->y<bb->y)
       return -1;
    return 0;
}
int comparare(struct pozitie stiva_r[],struct pozitie stiva_j[],int nst_r,int nst_j,int k){
     int i=0,j=0,x,y,ok=1;
     qsort(stiva_r,nst_r,sizeof(stiva_r[0]),compara);
     qsort(stiva_j,nst_j,sizeof(stiva_j[0]),compara);
     while (i<nst_r && j<nst_j && ok){
           if (stiva_r[i].x==stiva_j[j].x){
              if (stiva_r[i].y==stiva_j[j].y){
                 printf("%d %d %d\n",k+1,stiva_r[i].x,stiva_r[i].y);
                 return 0;
              }
              else if (stiva_r[i].y>stiva_j[j].y)
                   ++j;
              else if (stiva_r[i].y<stiva_j[j].y)
                   ++i;
           }
           else{
                if (stiva_r[i].x>stiva_j[j].x)
                   ++j;
                else
                    ++i;
           }
     }
     return 1;
}
void lee(){
     int k=1,i,pr,ur,pj,uj,nst_r=0,nst_j=0;
     struct pozitie e,f,stiva_r[MAX],stiva_j[MAX],acum;
     pr=pj=ur=uj=0;
     r[ur++]=romeo;
     j[uj++]=julieta;
     while (pr<ur && pj<uj){
           while (a[r[pr].x][r[pr].y]==k){
                 e=r[pr++];  /*   scot din coada lui romeo primul element     */
                 for (i=0;i<8;++i){
                     //x=e.x+dx[i];
                     //y=e.x+dy[i];
                     acum=(struct pozitie){e.x+dx[i],e.y+dy[i]};
                     if (a[acum.x][acum.y]==0){
                        a[acum.x][acum.y]=k+1;//a[e.x][e.y]+1;
                        r[ur++]=(struct pozitie){acum.x,acum.y};
                        stiva_r[nst_r++]=(struct pozitie){acum.x,acum.y};
                     }
                 }
           }
           while (b[j[pj].x][j[pj].y]==k){
                 f=j[pj++];  /*   scot din coada lui julieta primul element   */
                 for (i=0;i<8;++i){
                     //x=f.x+dx[i];
                     //y=f.x+dy[i];
                     acum=(struct pozitie){f.x+dx[i],f.y+dy[i]};
                     if (b[acum.x][acum.y]==0){
                        b[acum.x][acum.y]=k+1;//b[f.x][f.y]+1;
                        j[uj++]=(struct pozitie){acum.x,acum.y};
                        stiva_j[nst_j++]=(struct pozitie){acum.x,acum.y};
                     }
                 }
           }
           if (comparare(stiva_r,stiva_j,nst_r,nst_j,k)==0) // compar cele doua stive
              return;
           else{
                nst_r=0;
                nst_j=0;
                ++k;
           }
     }
}
void print(){
     int i,j;
     printf("%d %d %d %d\n",romeo.x,romeo.y,julieta.x,julieta.y);
     for (i=1;i<=n;++i){
         for (j=1;j<=m;++j)
             printf("%d ",a[i][j]);
         printf("\n");
     }
     printf("\n");
     for (i=1;i<=n;++i){
         for (j=1;j<=m;++j)
             printf("%d ",b[i][j]);
         printf("\n");
     }
     fclose(stdin);
     fclose(stdout);
     exit(0);
}
int main(){
    scan();
    lee();
    //print();
}