Cod sursa(job #942146)

Utilizator catalinutzbCraciun Catalin catalinutzb Data 20 aprilie 2013 23:53:01
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.64 kb
/// Craciun Catalin (c)
///      RJ
/*******************************

    Codificare: 1 = loc de plecare
               -1 = interzis
               -5 = unde trebuie sa ajung

*******************************/
#include <cstdio>
#include <cstring>
#include <iostream>
#define DMAX 10210
using namespace std;

struct matrice{

    short int lin,col;
};

FILE *f=fopen("rj.in","r");
FILE *g=fopen("rj.out","w");

short int R[101][101],J[101][101];
matrice pozR;
matrice pozJ;
matrice startR;
matrice startJ;
matrice stopR;
matrice stopJ;
short int n,m;
short int auxn,auxm;
char t[100];

void citire(){

    short int i,j;;

    fscanf(f,"%d %d",&n,&m);
    auxn=n;
    auxm=m;
    for (i=0;i<=n+1;i++)
        R[0][i]=J[0][i]=R[m+1][i]=J[m+1][i]=-1;
    for (i=0;i<=m+1;i++)
        R[i][0]=J[i][0]=R[i][n+1]=J[i][n+1]=-1;
    for (i=0;i<=n;i++){
        fgets(t,100,f);
        if (i>0){
            for (j=0;j<=strlen(t);j++){
                if (t[j]=='R'){
                    R[i][j+1]=1;
                    J[i][j+1]=-5;
                    pozR.lin=i;
                    pozR.col=j+1;
                    startR.lin=i;
                    startR.col=j+1;
                    stopJ.lin=i;
                    stopJ.col=j+1;
                }
                else if (t[j]=='J'){
                    J[i][j+1]=1;
                    R[i][j+1]=-5;
                    pozJ.lin=i;
                    pozJ.col=j+1;
                    startJ.lin=i;
                    startJ.col=j+1;
                    stopR.lin=i;
                    stopR.col=j+1;
                }
                else if (t[j]=='X')
                    R[i][j+1]=J[i][j+1]=-1;
            }
        }
    }
    fclose(f);
}

void leer(){

    short int k;
    matrice el;
    int prim,ultim;
    matrice C[DMAX];
    int dirl[]={0,1,0,-1,1,1,-1,-1};
    int dirc[]={1,0,-1,0,1,-1,-1,1};

    C[1]=startR;
    prim=1; ultim=1;

    while ((R[stopR.lin][stopR.col]==-5)&&(prim<=ultim)){
        el=C[prim];
        prim++;

        for (k=0;k<7;k++){
            if ((R[el.lin+dirl[k]][el.col+dirc[k]]==0)||(R[el.lin+dirl[k]][el.col+dirc[k]]==-5)){
                R[el.lin+dirl[k]][el.col+dirc[k]]=R[el.lin][el.col]+1;
                ultim++;
                C[ultim].lin=el.lin+dirl[k];
                C[ultim].col=el.col+dirc[k];
            }
        }
    }
}

void leej(){

    short int k;
    matrice el;
    int prim,ultim;
    matrice C[DMAX];
    int dirl[]={0,1,0,-1,1,1,-1,-1};
    int dirc[]={1,0,-1,0,1,-1,-1,1};

    C[1]=startJ;
    prim=1; ultim=1;

    while ((J[stopJ.lin][stopJ.col]==-5)&&(prim<=ultim)){
        el=C[prim];
        prim++;

        for (k=0;k<7;k++){
            if ((J[el.lin+dirl[k]][el.col+dirc[k]]==0)||(J[el.lin+dirl[k]][el.col+dirc[k]]==-5)){
                J[el.lin+dirl[k]][el.col+dirc[k]]=J[el.lin][el.col]+1;
                ultim++;
                C[ultim].lin=el.lin+dirl[k];
                C[ultim].col=el.col+dirc[k];
            }
        }
    }
}

void determinareminim(){

    short int i,j;

    int mini=100000;
    matrice p;

    for (i=1;i<=auxn;i++){
        for (j=1;j<=auxm;j++)
            if ((R[i][j]==J[i][j])&&(R[i][j]!=-1)&&(R[i][j]!=0)){
                if (R[i][j]<mini){
                    mini=R[i][j];
                    p.lin=i;
                    p.col=j;
                }
                else if (R[i][j]==mini){
                    if (j<p.col){
                       mini=R[i][j];
                        p.lin=i;
                        p.col=j;
                    }
                }
            }
    }

    fprintf(g,"%d %d %d",mini,p.lin,p.col);
    fclose(g);
}

int main(){

    citire();
    leer();
    leej();
    determinareminim();

    return 0;
}