Cod sursa(job #853208)

Utilizator Master011Dragos Martac Master011 Data 12 ianuarie 2013 11:10:24
Problema Rj Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <stdio.h>
#define MAX 110
#define DIM MAX*6

FILE *in,*out;

const int dl[]={-1,-1,0,1,1,1,0,-1};
const int dc[]={0,1,1,1,0,-1,-1,-1};

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

element cj[DIM],cr[DIM];
int matj[MAX][MAX],matr[MAX][MAX];
int incj=0,sfj=0,incr=0,sfr=0,n,m,min=1000000;
int ry,rx,jx,jy,y,x;

void init(int a, int b){
    incr=sfr=0;
    int i,j;
     for(i=1;i<=a;i++)
        for(j=1;j<=b;j++){
            if(matr[i][j]!=-1)
                matr[i][j]=0;
        }
    return;
}

void pushr(element P){
    cr[sfr++]=P;
    if(sfr==DIM)
        sfr=0;
    return;
}

int emtyr(){
    return incr==sfr;
}

element popr(){
    element Q;
    Q=cr[incr++];
    if(incr==DIM)
        incr=0;
    return Q;
}

void afisare(int a, int b){
    int i,j;
    for(i=1;i<=a;i++){
        for(j=1;j<=b;j++){
            fprintf(out,"%d  ",matr[i][j]);
        }
        fprintf(out,"\n");
    }

}

int romeo(){
    int i;
    element P,Q;
    P.y=ry;
    P.x=rx;
    matr[P.y][P.x]=1;
    //afisare(a,b);
   //fprintf(out,"%d %d %d\n\n",nrcr,destx,desty);
    pushr(P);
    while(!emtyr()){
        P=popr();
        if((matj[P.y][P.x]>0)&&(matr[P.y][P.x]==matj[P.y][P.x])){
            if(matj[P.y][P.x]<min){
                    min=matj[P.y][P.x];
                    y=P.y;
                    x=P.x;
                }
            if(matj[P.y][P.x]==min){
               if(P.y<y){
                    y=P.y;
                    x=P.x;
                }
                else
                    if((P.y==y)&&(P.x<x)){
                        x=P.x;
                    }
            }
        }
        for(i=0;i<8;i++){
            Q.y=P.y+dl[i];
            Q.x=P.x+dc[i];
            if(matr[Q.y][Q.x]==0){
                matr[Q.y][Q.x]=1+matr[P.y][P.x];
                pushr(Q);
            }
        }
    }
    return 0;
}

void pushj(element P){
    cj[sfj++]=P;
    if(sfj==DIM)
        sfj=0;
    return;
}

int emtyj(){
    return incj==sfj;
}

element popj(){
    element Q;
    Q=cj[incj++];
    if(incj==DIM)
        incj=0;
    return Q;
}
void julieta(){
    int i;
    element P,Q;
    P.y=jy;
    P.x=jx;
    matj[P.y][P.x]=1;
    pushj(P);
    while(!emtyj()){
        P=popj();
        for(i=0;i<8;i++){
            Q.y=P.y+dl[i];
            Q.x=P.x+dc[i];
            if(matj[Q.y][Q.x]==0){
                matj[Q.y][Q.x]=1+matj[P.y][P.x];
                pushj(Q);
            }
        }
    }
    return;
}

void bordare(int a,int b){
    int i;
    for(i=0;i<=a+1;i++){
        matj[i][0]=-1;
        matj[i][b+1]=-1;
        matr[i][0]=-1;
        matr[i][b+1]=-1;
    }
    for(i=0;i<=b+1;i++){
        matj[0][i]=-1;
        matj[a+1][i]=-1;
        matr[0][i]=-1;
        matr[a+1][i]=-1;
    }
    return;
}

int main(){
    in=fopen("rj.in","r");
    out=fopen("rj.out","w");
    int n,m;
    fscanf(in,"%d%d",&n,&m);
    bordare(n,m);
    int i,j;
    char s;
    for(i=1;i<=n;i++){
         s=fgetc(in);
        for(j=1;j<=m;j++){
            s=fgetc(in);
            if(s=='X'){
                matj[i][j]=-1;
                matr[i][j]=-1;
            }
            if(s=='R'){
                ry=i;
                rx=j;
            }
            if(s=='J'){
                jy=i;
                jx=j;
            }
        }
    }
    julieta();
    romeo();
    fprintf(out,"%d %d %d\n",min,y,x);
    fclose(out);
    fclose(in);
    return 0;
}