Cod sursa(job #2667630)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 3 noiembrie 2020 18:16:24
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<cstdio>

const int N=1<<7;
const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};

char s[N][N];
int nn,x[N*N],y[N*N],x1[N*N],y1[N*N],n,m,romeo[N][N],julieta[N][N];

void lee(int xx,int yy)
{
    for (int i=0;i<8;i++)
    {
        int d1=xx+dx[i],d2=yy+dy[i];
        if (d1>=0 && d1<n && d2>=0 && d2<m && romeo[d1][d2]==-1 && s[d1][d2]!='X')
        {
            nn++;
            x1[nn]=d1;
            y1[nn]=d2;
            romeo[d1][d2]=romeo[xx][yy]+1;
        }
    }
}

void leej(int xx,int yy)
{
    for (int i=0;i<8;i++)
    {
        int d1=xx+dx[i],d2=yy+dy[i];
        if (d1>=0 && d1<n && d2>=0 && d2<m && julieta[d1][d2]==-1 && s[d1][d2]!='X')
        {
            nn++;
            x1[nn]=d1;
            y1[nn]=d2;
            julieta[d1][d2]=julieta[xx][yy]+1;
        }
    }
}

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

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int xr,yr,xj,yj;
    scanf("%d%d\n",&n,&m);
    for (int i=0;i<n;i++)
    {
        gets(s[i]);
        for (int j=0;j<m;j++)
            if (s[i][j]=='R')
            {
                xr=i;
                yr=j;
            }
            else
            if (s[i][j]=='J')
            {
                xj=i;
                yj=j;
            }
    }
    init();
    int nr=1;
    x[1]=xr;
    y[1]=yr;
    romeo[xr][yr]=0;
    while (nr)
    {
        nn=0;
        for (int i=1;i<=nr;i++)
            lee(x[i],y[i]);
        nr=nn;
        for (int i=1;i<=nr;i++)
        {
            x[i]=x1[i];
            y[i]=y1[i];
        }
    }
    nr=1;
    x[1]=xj;
    y[1]=yj;
    julieta[xj][yj]=0;
    while (nr)
    {
        nn=0;
        for (int i=1;i<=nr;i++)
            leej(x[i],y[i]);
        nr=nn;
        for (int i=1;i<=nr;i++)
        {
            x[i]=x1[i];
            y[i]=y1[i];
        }
    }
    int timp=N*N*N,xxx,yyy;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            if (romeo[i][j]==julieta[i][j] && romeo[i][j]<timp && s[i][j]!='X' && romeo[i][j]!=-1)
            {
                timp=romeo[i][j];
                xxx=i;
                yyy=j;
            }
    printf("%d %d %d\n",timp+1,xxx+1,yyy+1);
    return 0;
}