Cod sursa(job #1837065)

Utilizator dumitru123Patularu Mihai dumitru123 Data 28 decembrie 2016 23:06:18
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
#define dmax 101
int n,m;
char a[dmax][dmax];
short romeo[dmax][dmax],julieta[dmax][dmax];
int start_r,stop_r,start_j,stop_j;
int x[]={0,-1,-1,0,1,1,1,0,-1},y[]={0,0,1,1,1,0,-1,-1,-1};
void Read()
{
    f>>n>>m;
    f.get();
    for(int i=1; i<=n; i++)
    {
        f.getline(a[i],101);
        for(int j=0; j<m; j++)
        {
            if(a[i][j]=='R')
            {
                romeo[i][j+1]=1;
                start_r=i;
                stop_r=j+1;
            }
            if(a[i][j]=='J')
            {
                julieta[i][j+1]=1;
                start_j=i;
                stop_j=j+1;
            }
            if(a[i][j]=='X') romeo[i][j+1]=julieta[i][j+1]=-1;
        }

    }
}
void Border()
{
    for (int i=0; i<=n+1; i++)
        romeo[i][0]=romeo[i][m+1]=-1;
    for (int i=0; i<=m+1; i++)
        romeo[0][i]=romeo[n+1][i]=-1;

    for (int i=0; i<=n+1; i++)
        julieta[i][0]=julieta[i][m+1]=-1;
    for (int i=0; i<=m+1; i++)
        julieta[0][i]=julieta[n+1][i]=-1;
}
void Lee_Romeo()
{
    int i,j;
    queue < pair <int , int> > coada;
    coada.push(make_pair(start_r,stop_r));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
       coada.pop();
       for(int k=1;k<=8;k++)
       {
           if(romeo[i+x[k]][j+y[k]]==0)
           {
            romeo[i+x[k]][j+y[k]]=romeo[i][j]+1;
           coada.push(make_pair(i+x[k],j+y[k]));
           }
       }
    }
}
void Lee_Julieta()
{
    int i,j;
    queue < pair <int , int> > coada;
    coada.push(make_pair(start_j,stop_j));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
       coada.pop();
       for(int k=1;k<=8;k++)
       {
           if(julieta[i+x[k]][j+y[k]]==0)
           {
            julieta[i+x[k]][j+y[k]]=julieta[i][j]+1;
           coada.push(make_pair(i+x[k],j+y[k]));
           }
       }
    }
}
void Find()
{
    int minim=1001,ox,oy;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(romeo[i][j]==julieta[i][j] and romeo[i][j]>1)
    {
        if(romeo[i][j]<minim)
        {
            minim=romeo[i][j];
            ox=i;
            oy=j;
        }
    }
    g<<minim<<" "<<ox<<" "<<oy;
}
int main()
{
    Read();
    Border();
    Lee_Romeo();
    Lee_Julieta();
    Find();
    return 0;
}