Cod sursa(job #946661)

Utilizator catalinutzbCraciun Catalin catalinutzb Data 5 mai 2013 14:52:50
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 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]>0 && R[i][j]<mini){
                mini=R[i][j];
                xm=i;
                ym=j;
            }
            else if (R[i][j]==J[i][j] && R[i][j]!=-1 && R[i][j]==mini){
                if (i<xm){
                   mini=R[i][j];
                    xm=i;
                    ym=j;
                }
                else if (i==xm){
                    if (j<ym){
                        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 (R[i][j]<0)
                cout<<R[i][j]<<" ";
            else
                cout<<" "<<R[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(){

    char c;

    f>>n>>m;
    Bordare();
    f>>noskipws;
    f.get();
    for (short int i=1;i<=n;i++){
        for (short int j=1;j<=m+1;j++){
            f.get(c);
            if (c=='\n')
                break;
            if (c=='R')
                J[i][j]=-5, R[i][j]=1, xr=i, yr=j;
            else if (c=='J')
                J[i][j]=1, R[i][j]=-5, xj=i, yj=j;
            else if (c=='X')
                J[i][j]=R[i][j]=-1;
        }
    }
    f.close();
}

int main(){

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

	return 0;
}