Cod sursa(job #1691504)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 18 aprilie 2016 16:26:45
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <fstream>
#include <queue>
#include <string>

using namespace std;

ifstream in("rj.in");
ofstream out("rj.out");

int n,m;
int matrR[104][104];//-2 obstacole,-1 spatii,0 r, 0 j
int matrJ[104][104];
string x;
queue< pair<int,int> > coada;
int xr,yr,xj,yj;
int dx[]={0,0,1,0,-1,-1,1,-1,1};
int dy[]={0,1,0,-1,0,-1,1,1,-1};

bool verifR(int x,int y)
{
    if(x>=1 && x<=n && y>=1 && y<=m && matrR[x][y]==-1) return 1;
    return 0;
}

bool verifJ(int x,int y)
{
    if(x>=1 && x<=n && y>=1 && y<=m && matrJ[x][y]==-1) return 1;
    return 0;
}

void leeRomeo(int x,int y)
{
    int i,j,i2,j2,k;
    coada.push(make_pair(x,y));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(k=1;k<=8;k++)
        {
            i2=i+dx[k];
            j2=j+dy[k];
            if(verifR(i2,j2))
            {
                matrR[i2][j2]=1+matrR[i][j];
                coada.push(make_pair(i2,j2));
            }
        }
    }
}

void leeJulieta(int x,int y)
{
    int i,j,i2,j2,k;
    coada.push(make_pair(x,y));
    while(!coada.empty())
    {
        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for(k=1;k<=8;k++)
        {
            i2=i+dx[k];
            j2=j+dy[k];
            if(verifJ(i2,j2))
            {
                matrJ[i2][j2]=1+matrJ[i][j];
                coada.push(make_pair(i2,j2));
            }
        }
    }
}

int main()
{
    int i,j;
    int raspX,raspY;
    int tmin=100005;
    in>>n>>m;
    getline(in,x);
    for(i=1;i<=n;i++)
    {
        getline(in,x);
        for(int j=0;j<x.size();j++)
        {
            if(x[j]=='R')
            {
                matrR[i][j+1]=1;
                matrJ[i][j+1]=1;
                xr=i;
                yr=j+1;
            }
            if(x[j]=='J')
            {
                matrR[i][j+1]=1;
                matrJ[i][j+1]=1;
                xj=i;
                yj=j+1;
            }
            if(x[j]=='X')
            {
                matrJ[i][j+1]=-2;
                matrR[i][j+1]=-2;
            }
            if(x[j]==' ')
            {
                matrJ[i][j+1]=-1;
                matrR[i][j+1]=-1;
            }
        }
        for(j=x.size();j<=m;j++)
        {
            matrR[i][j+1]=-1;
            matrJ[i][j+1]=-1;
        }
    }
    leeRomeo(xr,yr);
    leeJulieta(xj,yj);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(matrJ[i][j]==matrR[i][j] && matrJ[i][j]!=1 && matrJ[i][j]!=-2 && matrJ[i][j]!=-1)
            {
                if(matrJ[i][j]<tmin)
                {
                    tmin=matrJ[i][j];
                    raspX=i;
                    raspY=j;
                }
            }
        }
    out<<tmin<<" "<<raspX<<" "<<raspY;
    in.close();
    out.close();
    return 0;
}