Cod sursa(job #378147)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 27 decembrie 2009 18:57:12
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <stdio.h>
#define Max 102
#define OO 0x3f3f3f3f

using namespace std;

short int R[Max][Max], J[Max][Max];
short int dl[8]={-1,-1,0,1,1,1,0,-1}, dc[8]={0,1,1,1,0,-1,-1,-1};
short int N, M;
short int lr,cr,lj,cj;

struct coada {
 short int lin;
 short int col;
};

void BF(short int mat[Max][Max], short int x, short int y) {
 short int st=1, sf=1, u, v;
 coada c[Max*Max];
 c[st].lin=x;
 c[st].col=y;
 while(st<=sf) {
    for(short int i=0; i<8; i++) {
        u=c[st].lin+dl[i]; v=c[st].col+dc[i];
        if(!mat[u][v]) {
            sf++;
            c[sf].lin=u;
            c[sf].col=v;
            mat[u][v]=mat[c[st].lin][c[st].col]+1;
        }
    }
    st++;
 }
}

void MinPoz(int &tmin,int &xmin,int &ymin) {
 for(int i=1;i<=N;i++) {
    for(int j=1;j<=M;j++) {
        if( R[i][j]!=-1 && R[i][j]!=0 && R[i][j]==J[i][j]) {
            if(tmin>R[i][j]) {
                tmin=R[i][j];
                xmin=i;
                ymin=j;
            } else
                if(tmin==R[i][j]) {
                    if(xmin>i)
                        {xmin=i; ymin=j;}
                    else
                        if(xmin==i) {
                            if(ymin>j)ymin=j;
                        }
            }
        }
    }
 }
}

int main() {
 FILE *fin=fopen("rj.in", "r"), *fout;

 char s[Max];
 fscanf(fin, "%d%d", &N, &M); fgets(s, Max, fin); *s=NULL;
 for(int i=1;i<=N;i++) {
    fgets(s, Max, fin);
    for(int j=0; j<M; j++)
      switch (s[j]) {
        case 'R': {R[i][j+1]=1;lr=i;cr=j+1; break;}
        case 'J': {J[i][j+1]=1;lj=i;cj=j+1; break;}
        case 'X': {R[i][j+1]=J[i][j+1]=-1;}
      }
    *s=NULL;
    }
//Bordare
 for(int i=0;i<=M+1;i++) {
    R[0][i]=J[0][i]=-1;
    R[N+1][i]=J[N+1][i]=-1;
 }
 for(int i=0;i<=N+1;i++) {
    R[i][0]=J[i][0]=-1;
    R[i][M+1]=J[i][M+1]=-1;
 }
 fclose(fin);

 BF(R,lr,cr);
 BF(J,lj,cj);

 int tmin,xmin,ymin;
 tmin=xmin=ymin=OO;

 MinPoz(tmin,xmin,ymin);
 fout=fopen("rj.out", "w");
 fprintf(fout,"%d %d %d",tmin,xmin,ymin);
 fclose(fout);
 return 0;
}