Cod sursa(job #946652)

Utilizator catalinutzbCraciun Catalin catalinutzb Data 5 mai 2013 13:28:40
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
/// Craciun Catalin
///  RJ
///   Campion - http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=898
///             Codificare: -1 = Interzis
///                         -5 = Locul in care trebuie sa ajung
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

struct matrice{

    short int lin;
    short int col;
};

short int n,m;
int xr,yr,xj,yj; /// Pozitiile lui Romeo si Julieta
char A[102][102];
int R[102][102];
int J[102][102];

void Parcurgere(){

    long mini=100000,xm=-1,ym=-1;

    for (short int i=1;i<=n;i++){
        for (short int j=1;j<=m;j++){
            if (R[i][j]==J[i][j] && R[i][j]!=-1 && R[i][j]<mini){
                mini=R[i][j];
                xm=i;
                ym=j;
            }
        }
    }

    g<<mini<<" "<<xm<<" "<<ym;
    g.close();
}

void LeeJ(){

    matrice C[20000]; /// Coada
    matrice el;
    short int prim=1,ultim=1;
    short int dx[]={1,0,-1,0,1,-1,-1,1};
    short int dy[]={0,1,0,-1,1,-1,1,-1};

    C[1].lin=xj;
    C[1].col=yj;

    while (prim<=ultim){

        el=C[prim];
        prim++;

        for (short int i=0;i<8;i++){
            if ((J[el.lin+dx[i]][el.col+dy[i]]==0)||(J[el.lin+dx[i]][el.col+dy[i]]==-5)){
                    ultim++;
                    C[ultim].lin=el.lin+dx[i];
                    C[ultim].col=el.col+dy[i];
                    J[el.lin+dx[i]][el.col+dy[i]]=J[el.lin][el.col]+1;
            }
        }
    }
}

void LeeR(){

    matrice C[20000]; /// Coada
    matrice el;
    short int prim=1,ultim=1;
    short int dx[]={1,0,-1,0,1,-1,-1,1};
    short int dy[]={0,1,0,-1,1,-1,1,-1};

    C[1].lin=xr;
    C[1].col=yr;

    while (prim<=ultim){

        el=C[prim];
        prim++;

        for (short int i=0;i<8;i++){
            if ((R[el.lin+dx[i]][el.col+dy[i]]==0)||(R[el.lin+dx[i]][el.col+dy[i]]==-5)){
                    ultim++;
                    C[ultim].lin=el.lin+dx[i];
                    C[ultim].col=el.col+dy[i];
                    R[el.lin+dx[i]][el.col+dy[i]]=R[el.lin][el.col]+1;
            }
        }
    }
}

void Afisare(){

    for (short int i=0;i<=n+1;i++){
        for (short int j=0;j<=m+1;j++)
            if (J[i][j]<0)
                cout<<J[i][j]<<" ";
            else
                cout<<" "<<J[i][j]<<" ";
        cout<<endl;
    }
}

void Bordare(){

    for (short int i=0;i<=n+1;i++)
        R[i][0]=R[i][m+1]=J[i][0]=J[i][m+1]=-1;
    for (short int i=0;i<=m+1;i++)
        R[0][i]=J[0][i]=R[n+1][i]=J[n+1][i]=-1;
}

void Citire(){

    short i,j;
    bool yes=0;
    char c;

    f>>n>>m>>noskipws;
    Bordare();
    for(i=1;i<=n;i++){

       if(yes==0)
            f>>c;
       yes=0;
       for(j=1;j<=m;j++){
            f>>A[i][j];
            if(A[i][j]=='\n'){
                yes=1;
                while(j<=m){
                    A[i][j]=' ';
                    j++;
                }
                break;
            }
            if(A[i][j]=='R'){
                R[i][j]=1;
                J[i][j]=-5;
                xr=i;
                yr=j;
            }
            if(A[i][j]=='J'){
                J[i][j]=1;
                R[i][j]=-5;
                xj=i;
                yj=j;
            }
            if(A[i][j]=='X')
                R[i][j]=J[i][j]=-1;
        }
    }
    f.close();
}

int main(){

    Citire();

    LeeR();
    LeeJ();
    Afisare();
    Parcurgere();

	return 0;
}