Cod sursa(job #865711)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 26 ianuarie 2013 21:03:06
Problema Rj Scor 100
Compilator cpp Status done
Runda 23_reloaded_1 Marime 2.59 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <queue>

#define pp pair<int,int>
#define ox first
#define oy second

#define Nmax 102

using namespace std;

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

int mat[Nmax][Nmax];
int romeo[Nmax][Nmax];
int julieta[Nmax][Nmax];

int n,m,sol,poz1,poz2,k;
char c;
int xR,yR,xJ,yJ;

queue <pp> QR,QJ;

void citire(){

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

    fscanf(f,"%d%d%c",&n,&m,&c);

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m+1; j++){

            fscanf(f,"%c",&c);

            if(c!='\n'){

                if(c==' ')
                    mat[i][j]=0;
                else
                    if(c=='R'){
                        xR=i;
                        yR=j;
                    }
                    else
                        if(c=='J'){
                            xJ=i;
                            yJ=j;
                        }
                        else
                            if(c=='X')
                                mat[i][j]=-1;
            }


        }
}

void bordare(){

    for(int i=0;i<=m+1;i++)
        mat[0][i]=mat[n+1][i]=-1;

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


void lee(){

    pp current,v;
    sol=-1;

    QR.push(make_pair(xR,yR));
    QJ.push(make_pair(xJ,yJ));

    romeo[xR][yR]=1;
    julieta[xJ][yJ]=1;

    while(!QR.empty() || !QJ.empty()){

        current=QR.front();

        for(k=0;k<8;k++){

            v.ox=current.ox+dl[k];
            v.oy=current.oy+dc[k];

            if(romeo[v.ox][v.oy]==0 && mat[v.ox][v.oy]==0){

                romeo[v.ox][v.oy]=romeo[current.ox][current.oy]+1;
                QR.push(make_pair(v.ox,v.oy));
            }
        }

        QR.pop();

        current=QJ.front();

        for(k=0;k<8;k++){

            v.ox=current.ox+dl[k];
            v.oy=current.oy+dc[k];

            if(julieta[v.ox][v.oy]==0 && mat[v.ox][v.oy]==0){

                julieta[v.ox][v.oy]=julieta[current.ox][current.oy]+1;
                QJ.push(make_pair(v.ox,v.oy));
            }
        }

        QJ.pop();
    }
}

void gaseste(){

    sol=100000;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(romeo[i][j]==julieta[i][j] &&
            romeo[i][j] && julieta[i][j] &&
            sol>romeo[i][j]){
                sol=romeo[i][j];
                poz1=i;
                poz2=j;
            }

}

void afis(){

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

    fprintf(g,"%d %d %d",sol,poz1,poz2);
}

int main()
{
    citire();
    bordare();
    lee();
    gaseste();
    afis();

    return 0;
}